[Python]11055번, 가장 큰 증가하는 부분 수열

목차

 

문제

 

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}인 경우에 합이 가장 큰 증가하는 부분 수열은

A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. $(1 ≤ A_i ≤ 1,000)$

 

출력

 

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

풀이

 

이 문제는 쓰여있는 대로 주어진 수열의 증가하는 부분수열 중 합이 최대인 경우를 찾는 것이다.

 

예를 들어 [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]이라는 수열에서 증가하는 수열이란

 

[1, 2, 50, 60], [1, 2, 3, 5, 6, 7, 8]과 같은 수열을 말한다. 이 중 합이 가장 큰 수열을 찾아 그 합을 출력하면 된다.

 

문제를 푸는 알고리즘을 말로 풀어 설명하면 대략 다음과 같은 과정을 거친다.

 

1. DP리스트 초기화
   가장 먼저 'dp'리스트를 만들어 주어진 수열을 그대로 저장한다. 이렇게 하는 이유는 각 숫자 하나만으로 이루어진
   부분 수열의 합이 자기 자신이기 때문이다.
2. 이중 반복문을 이용한 탐색
   이어서 각 숫자를 하나씩 순회하면서 그 숫자를 마지막으로 하는 증가 부분 수열 중 최대 합을 'dp'에 저장해야 한다.
   이를 위해
   1. 현재 숫자보다 앞의 숫자들을 모두 확인하고
   2. 현재 숫자보다 작은 숫자가 있다면 그 숫자까지의 최대 증가 부분 수열의 합과 현재 숫자를 합한 값을
      현재 위치의 'dp'값과 비교해 큰 값으로 갱신한다.
   3. 이런 식으로 모든 숫자를 확인하면 그 자체로 해당 숫자까지의 최대 합을 저장한 리스트가 된다.
3. 'dp'리스트 중 최댓값을 출력한다.

주어진 예시[1, 100, 2, 50, 60, 3, 5, 6, 7, 8]에 따라 문제를 풀면 다음과 같은 과정을 거치게 된다.

 

1. dp[0]는 1이다.
2. 두 번째 숫자 100에 대해서는 앞에 그보다 작은 1이 있으므로, 이를 더한 101과 100중 더 큰 값인 101을 dp[1]에 저장한다.
3. 세 번째 숫자 2에 대해서는 앞에 숫자 1과 100이 있으므로, 작은 값인 1을 더해 3으로 갱신한다.
4. 네 번째 숫자 50에 대해서는 같은 논리로 1, 2를 더해 53을 저장한다.
5. 다섯 번째 숫자 60에 대해서든 1, 2, 50을 더한 113을 저장한다.
6. 이런 식으로 리스트의 끝까지 반복한다.
7. 순회가 끝난 리스트의 최댓값은 113이므로, 해당 숫자를 출력한다.

계속해서 이 알고리즘을 코드로 표현해보자.

 

Python

 

import sys

N = int(sys.stdin.readline().rstrip())
lst = list(map(int, sys.stdin.readline().split()))

dp = lst.copy()

for i in range(N):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i], dp[j] + lst[i])

print(max(dp))

설명에 비해 코드가 간단하다.

 

동적계획법 문제는 답을 보면 쉽지만 거기까지 다다르기가 수월하지만은 않은 것 같다.

 

기존의 생각 방법을 벗어난 사고를 해야 하기 때문인지도 모른다.

 

어쨌거나 가장 간단한 방법으로 11055번, 가장 큰 증가하는 부분 수열 문제를 풀어보았다.

 

끝!