[백준] 11055 : 가장 큰 증가하는 부분 수열 (파이썬 / Python)

가장 큰 증가하는 부분 수열

https://www.acmicpc.net/problem/11055

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를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

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

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

---

코드

N = int(input())
A = list(map(int, input().split()))
d = [0] * N

d[0] = A[0]

for i in range(N):
    for j in range(i):
    	if A[i] > A[j]:
        	d[i] = max(d[i], d[j] + A[i])
        else:
        	d[i] = max(d[i], A[i])
            
print(max(d))

풀이

이 문제는 11053번 문제와 매우 유사하다. 증가하는 부분 수열의 길이 대신 합을 구하는 배열 d를 구하면 된다.

만약 A[i] > A[j]라면, 기존의 d[i]와 새로 더해져 구해지는 d[j] + A[i] 중 큰 값을 d[i]로 갱신하면 된다.

만약 A[i] <= A[j]라면, 기존의 d[i]와 A[i] 중 큰 값으로 갱신하면 된다. 이 과정을 수행해주어야 하는 이유는 극단적으로 해당 인덱스에서 증가하는 부분수열이 전혀 만들어지지 않을 경우, 뒤의 과정의 수행을 위해 현재값(A[i])이라도 할당해주어야 하기 때문이다. 즉, 뒤의 과정에서 해당 인덱스부터 시작하는 부분 수열을 고려해주어야 한다는 뜻이다.