[백준 14003] 가장 긴 증가하는 부분 수열 5 (Platinum 5)

문제

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

요약

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

분류

• 다이나믹 프로그래밍
• 이분 탐색

풀이

1. 내 풀이 (DP)

O(NlogN) 알고리즘을 통해 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])