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

문제.

 

 

풀이.

https://turret1234.tistory.com/138

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

기본적으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 위의 링크와 같다.

여기서 추가적으로 경로를 담아야하는데.

경로를 담는 dp배열을 추가하여 연산마다 경로를 담아준다.

 

소스코드.

import sys

input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
dp = [[0, []] for i in range(n)]
dp[0][0] = 0

for i in range(n):
    dp[i][1].append(numbers[i])
    for j in range(i):
        if numbers[i] > numbers[j] and dp[i][0] < dp[j][0]:
            dp[i][0] = dp[j][0]
            dp[i][1] = dp[j][1] + [numbers[i]]
    dp[i][0] += 1
dp.sort(key = lambda x: x[0])
print(dp[-1][0])
for i in dp[-1][1]:
    print(i, end=' ')