백준 | 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

크기 n(1 이상 1000 이하)인 수열이 주어질 때,
가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.

dp[i]를 i번째 원소까지 가장 긴 부분 수열의 길이라 정의하자.

dp[i]를 구하려면..
어찌되었건 수열의 0번째 원소부터 (i - 1)번째 원소를 순차적으로 탐색해야 할 것이다.

i번째 원소가 기준 값이 되기 때문에,
현재 탐색 중인 j번째 원소가 i번째 원소보다 작을 경우를 살펴보아야 한다.

j번째 원소와 i번째 원소 사이의 값을 다 무시한다고 가정했을 때,
'j번째 원소에서 i번째 원소로 하나 증가한 수열'의 길이가 dp[i]가 될 수 있기 때문이다.
(dp[j]는 j번째 원소까지 가장 긴 부분 수열의 길이일 것이다.)

그래서 dp[i] = max(dp[i], dp[j] + 1)과 같이 점화식을 세울 수 있다.

코드(정답)는 다음과 같다.

import sys


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

dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if ary[i] > ary[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

이 문제를 동적 계획법 즉, DP로 접근해도 되는 이유는..
수열의 크기 n의 최댓값이 1,000이기 때문이다.

DP는 보통 O(N^2)의 시간 복잡도를 갖는데,
N이 1,000인 경우도 최대 1,000,000번 정도의 연산이 발생하므로 충분히 처리 가능하다.