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

백준 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열 문제이다.

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

0번째부터 (i - 1)번째 원소를 순차적으로 탐색하면서, 해당 탐색의 기준점이라 할 수 있는 i번째 원소보다 큰 원소가 있다면, 그 원소(j)의 dp[j] 값에 1을 더한 값이 dp[i]의 후보이다.

또 다른 후보는 그 시점에 저장된 dp[i]의 값이다.

따라서 해당 시점에서 dp[j] + 1, dp[i] 중 큰 값이 dp[i]이다.

import sys


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

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

print(max(dp))

아래의 코드도 가능하다.

import sys


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

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

print(max(dp))