[DP] 백준 #14402 가장 긴 증가하는 부분 수열 4 - Python

🗂️ 문제

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

 

💡 접근법

DP를 통해 LIS를 푸는 문제의 응용편이다.

 

i번째까지 순열에 대해 증가하는 순열인 경우이면서 부분 순열의 길이가 더 길어질 때, dp에 현재까지의 부분 순열을 저장한다.

이후, 가장 길이가 큰 부분 순열에 대해 부분 순열의 길이와 부분 순열을 출력한다.

 

😎 내 코드

import sys

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

dp = [[arr[i]] for i in range(N)]

for i in range(1, N):
    for j in range(i):
        if arr[i] > arr[j] and len(dp[j]) + 1 > len(dp[i]):
            dp[i] = dp[j] + [arr[i]]

print(len(max(dp, key=len)))
print(*max(dp, key=len))

 

🧐 배운 점

• 출력값을 형식에 맞지 않게 출력하여 계속 에러가 발생했다. 출력 형식을 잘 확인하자…

 

✅ 정답 확인