[백준] 14002번-(Python 파이썬) - DP

문제링크 : https://www.acmicpc.net/problem/14002

저번에 풀었던 lis문제와 비슷한 문제 유형이다.
각 수마다 자신보다 앞에 있는 수이면서 작은 숫자들 중
가장 큰 길이를 구해 그 길이에 +1 을 해주며
다른 배열에 그 값들을 추가해 준 뒤
출력해주면 되는 문제이다.

import sys
input = sys.stdin.readline

n = int(input())
s = list(map(int, input().split()))
dp = [0 for _ in range(n)]
array = [[x] for x in s]

for i in range(n):
  for j in range(i):
    if s[i] > s[j] and dp[i] < dp[j]:
      array[i] = array[j] + [s[i]]
      dp[i] = dp[j]
  dp[i] += 1

length = 0
flag = 0
for i in range(n):
  if length < dp[i]:
    flag = i
    length = dp[i]

print(length)
print(*array[flag])