백준 14003 가장 긴 증가하는 부분 수열 5 - 파이썬

문제.

 

풀이.

O(NlogN)로 문제를 풀어야한다.

https://turret1234.tistory.com/151

백준 12015 가장 긴 증가하는 부분 수열2 - 파이썬

기본적인 풀이방법은 위 링크와 같다.

여기서 경로를 저장한 배열을 만들고 연산마다 경로를 추가하여주면된다.

 

소스코드.

import sys
from bisect import bisect_left

input = sys.stdin.readline

n = int(input())
numbers = [0] + list(map(int, input().split()))
dp = [0] * (n+1)
cmp = [-1000000001] # 현재 인덱스 저장
maxvalue = 0


for i in range(1, n+1):
    if cmp[-1] < numbers[i]:
        cmp.append(numbers[i])
        dp[i] = len(cmp) - 1
        maxvalue = dp[i]
    else:
        dp[i] = bisect_left(cmp, numbers[i])
        cmp[dp[i]] = numbers[i]
print(maxvalue)

result = []
for i in range(n, 0, -1):
    if dp[i] == maxvalue:
        result.append(numbers[i])
        maxvalue -= 1
result.reverse()
print(*result)