[Baekjoon] 11055: 가장 큰 증가 부분 수열

문제

가벼운 11053: 가장 긴 증가하는 부분 수열에서 변형된 가벼운 dp 문제이다

 

풀이

내 풀이

import sys

n = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = seq[:]

dp[0] = seq[0]
for i, v in enumerate(seq):
    for j in range(i-1, -1, -1):
        if seq[j] < v:
            dp[i] = max(dp[i], v+dp[j])

print(max(dp))

해당 문제는 제일 큰 수의 합을 기억하며 나아가는 해법을 찾아가야 한다.

처음 제출했을때 dp 리스트를 모두 0으로 채워놓고 시작했는데, 현재 값보다 작은 값이 발견이 안됐을 때 0으로 처리되어 오답을 얻었다.

추후에 seq를 복사하여 구현했지만 seq 자체를 사용해서 구현해도 됐었다.

 

회고

11053문제에서 살짝 변형된거라 크게 어렵지 않았고 다른 문제들의 풀이도 비슷한 것 같다.

dp 문제에 조금 익숙해진 것 같다. 좀 더 풀어봐야겠다.