백준 알고리즘 - 가장 큰 증가 부분 수열(11055번)[Python]

문제

 

문제 상황

- 증가하는 부분수열 중 합이 가장 큰 것을 찾아야한다. 증가하는 수열 중 어떤 선택을 할 때 다음에 올 수 있는 요소들에 영향을 미치므로 DP를 활용한다. 

 

해결 전략

- i 와 j로 n^2의 순회를 해주며 a[i] > a[j]일 때에만 비교를 하도록 한다. 

코드 

n, a = int(input()), list(map(int, input().split()))
dp = a[:]
for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[j]+a[i], dp[i])
print(max(dp))

해설

새로 학습한 것 & 실수

- dp를 초기화 할 때, a리스트의 값을 넣는게 아니라 0으로 초기화 했다. [0 for _ in range(n)] 

- 이렇게 초기화를 하면, 모든 수열이 내림차순일 때 모든 값이 0이 된다. 

- 구하는 것이 갯수가 아니라 합이므로 초기화를 기본값으로 해야한다.