백준_11053_가장 긴 증가하는 부분수열(DP)

n = int(input())
a = list(map(int, input().split()))

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

현재 i를 기준으로 그 다음 숫자들을 돌면서 i의 수보다 큰 수가 나오면 해당 인덱스의 dp에 1을 더해준다.

1을 더해줄 때 현재 dp와 1을 더한 수를 비교해서 더 큰 값을 저장하기 때문에 가장 긴 증가하는 부분수열을 구할 수 있다.
예를들면 30의 경우 10 -> 20 -> 30 이경우와 20 -> 30, 10 -> 30 이렇게 3가지 증가하는 부분수열 나오는데 max를 통해 수열의 길이를 항상 큰 값으로 유지한다.

스스로 해결하지 못했다. 알고 보면 정말 간단해 보이기도 하고 이해하는 것도 쉬었지만 이러한 방식을 스스로 떠올리기엔 아직은 힘든 것 같다.