[백준] 14002: 가장 긴 증가하는 부분 수열 4

DP + Memorization

가장 긴 증가하는 부분 수열 4

이 문제는 수열의 크기와 범위가 1000으로 n^2의 DP로 풀 수 있는 문제이다. 그럼 DP 에 저장된 정보는 부분 수열의 길이 일테지.
DP 의 값이 4이면 해당 인덱스의 lst값이 부분 원소를 4개 가지고 있다는 말이니까 DP의 값이 큰 것부터 하나씩 감소해가면서 해당 원소의 값을 배열에 저장해서 뒤집으면 가장 긴 증가하는 부분 수열을 구할 수 있다.

import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
dp = [1] * n
d = [0] * n
for i in range(n):
	for j in range(i):
		if lst[i] > lst[j]:
			dp[i] = max(dp[i], dp[j]+1)
maxVal = max(dp)
res = []
for i in range(len(dp)-1, -1, -1):
	if dp[i] == maxVal:
		res.append(lst[i])
		maxVal -= 1
res.reverse()
print(max(dp))
print(*res)