[BOJ] Python 백준 가장 큰 증가하는 부분 수열(11055)

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

 

DP의 대표적인 문제라고 할 수 있다. 여기서 주의할 점은 갯수가 아닌 값을 더해서 최댓값을 찾는 것이다.

우선 dp 테이블을 s와 동일하도록 구성해주고, j 부터 i까지 가는 도중에 s[j] < s[i] 성립하는 경우에 증가하는 부분수열의 조건을 성립하는 것이기에, dp[i] = max(dp[i],dp[j] + s[i]) 로 dp[i] 값을 갱신해준다.

import sys
input = sys.stdin.readline

N = int(input())

s = list(map(int,input().split()))

dp = s[:]
for i in range(N):

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

print(max(dp))

 

회고.

처음에 가장 큰 증가하는 부분 수열을 dp테이블 초기화 과정에서 0으로 초과해 틀렸었다. 증가값의 합을 구하는 것이기에 s배열로 초기화해줘야 했는데 그부분에서 미스가 났다,,