[백준 14002] 가장 긴 증가하는 부분 수열 4 (Gold 4)

문제

[백준] 가장 긴 증가하는 부분 수열 4 (Gold 4)

요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하여라. 단, A의 크기는 1보다 크고 1,000보다 작으며, A(i)도 1보다 크고 1,000보다 작다.

분류

• 다이나믹 프로그래밍

풀이

1. 내 풀이 (DP)

A의 크기가 작고, A(i)는 음수가 아니기 때문에 O(N^2) 알고리즘으로 쉽게 구할 수 있다. 이후 dp를 역으로 순회하며 각 인덱스에 해당하는 숫자들을 뽑는다.

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

dp = [1] * n
ans = [0] * n

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

m = max(dp)
print(m)
ans = []
for i in range(n - 1, -1, -1):
    if m == 0:
        break
    if dp[i] == m:
        ans.append(arr[i])
        m -= 1
print(*ans[::-1])