백준 - 14002번(DP, LIS)

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

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

import sys
from collections import deque
n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))

dp = [1 for _ in range(n+1)]

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

dp.pop()
key = max(dp)
print(key)

ans = deque([])

while key > 0:
    for i in range(len(dp)-1,-1,-1):
        if dp[i] == key:
            ans.appendleft(arr[i])
            key = key - 1

print(*ans)

dp를 만들어주는 과정 자체는 이전 LIS 문제들과 완전히 동일하다.

dp에서 맨 뒤에 존재하는 1을 pop으로 제거해 주고

가장 큰 값(LIS의 길이)이 기준이 되기 때문에 max 함수를 사용해서 찾아준다.

해당 값을 리스트의 뒤에서부터 순서대로 찾아주면 맞는 원소를 모두 출력할 수 있다.

LIS에 대한 이해만 제대로 있다면 쉽게 푸는 문제다.