백준 11053번 python 풀이 - 가장 긴 증가하는 부분 수열

문제 링크

11053번

해결책

import sys

num_list = []
N = int(sys.stdin.readline())

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



dp = [1 for j in range(N+1)]

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

print(max(dp))

주석으로 달 설명

DP. 너무나 열받는 문제. 계속 시작지점을 i값으로 생각하던 것이 문제였다.

i의 값을 가장 긴 수열의 마지막으로 생각하면 금방 해결할 수 있다.

이런식의 분할은 도대체 뭘 떠올려야 할까?