[알고리즘][백준] 14002번 가장 긴 증가하는 부분 수열 4 - 파이썬(python) 풀이

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

---

11053번 가장 긴 증가하는 부분 수열의 응용 문제로 부분 수열의 길이 출력에 부분 수열까지 출력하는 문제이다.

 

이미 앞 문제에서 수열 길이를 max(dp)로 출력하였고

 

dp에서 1~max(dp)인 순서대로 a 수열에서 뽑아오면 되는 문제이다

 

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
dp = [1] * n
result = []

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

dm = max(dp)

for i in range(n-1, -1, -1):
    if dp[i] == dm:
        result.append(a[i])
        dm -= 1

print(max(dp))
print(*result[::-1])

 

result[::-1] 대신 result.reverse()도 사용가능하다

14002_가장긴증가하는부분수열4.py

0.00MB