[백준/Python] 14002번 - 가장 긴 증가하는 부분 수열 4

문제

백준 14002번 - 가장 긴 증가하는 부분 수열 4

해결 과정

• 비슷한 문제: 백준 11053번 - 가장 긴 증가하는 부분 수열
• 부분수열의 길이가 max(dp)니까 가장 긴 길이부터 -1씩 해당 하는 값들을 arr에 넣는다.
• arr.reverse() 거꾸로 정렬하는 것

시행착오

• 그러한 수열이 여러가지인 경우 아무거나 출력한다. 이게 무슨 뜻이지? = 부분 수열을 출력하라는 뜻..

풀이

import sys

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

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

# 부분 수열의 길이
print(max(dp))

arr = []
m = max(dp)
for i in range(n-1,-1,-1):
  if dp[i] == m:
    arr.append(num[i])
    m -= 1

arr.reverse()
print(*arr)