[Python/파이썬] 백준 14002번: 가장 긴 증가하는 부분 수열 4

문제

 

풀이

수열의 최대 크기가 1000이므로 N² 으로 풀면 된다.

dp 값을 갱신하는 방법과 동일하게 dp 수열도 갱신해주면 된다.

(아래 코드 참고) 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dpMax = [0] * n
dpArr = [[] for _ in range(n)]
dpArr[0] = [arr[0]]
maxIdx = 0

for i in range(1, n):
    for j in range(i - 1, -1, -1):
        if arr[i] > arr[j]:
            if dpMax[j] + 1 > dpMax[i]:
                dpMax[i] = dpMax[j] + 1
                dpArr[i] = dpArr[j][:]
    dpArr[i].append(arr[i])
    if dpMax[maxIdx] < dpMax[i]:
        maxIdx = i
        

print(dpMax[maxIdx] + 1)
for a in dpArr[maxIdx]:
    print(a, end = " ")

 

마무리

가장 긴 증가하는 부분 수열은 비슷한 유형이 많아서 비교적 쉽게 풀 수 있었다.