[백준] 14002 가장 긴 증가하는 부분 수열 4 (파이썬)

이전에 포스팅 했던 11779번과 같은 방법으로 dp값이 증가할 때 몇번째에서 왔는지를 저장하고 역순으로 따라가면 되는 문제다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n+1)]
route = [-1 for _ in range(n+1)]

for i in range(n):
  for j in range(i):
    if arr[i] > arr[j]:
      tmp = dp[i]
      dp[i] = max(dp[i], dp[j]+1)
      if dp[i] != tmp:
        route[i] = j

idx = dp.index(max(dp))
dq = deque([])
while idx >= 0:
  dq.appendleft(arr[idx])
  idx = route[idx]

print(max(dp))
while dq:
  print(dq.popleft(), end=" ")