백준 14002번: 가장 긴 증가하는 부분 수열 4 (Python)

접근

이번 문제는 입력 받는 수열의 길이가 길지 않아 전체를 다 탐색하는 dp 알고리즘을 이용하였다.

dp 알고리즘으로 길이만 구하는 문제: 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

이전 문제와는 다르게 해당 수열을 구해야 한다는 점이 다르다. 따라서 dp에 부분 수열의 길이만 저장하는 것이 아닌, 해당 길이의 부분 수열을 같이 저장할 수 있도록 코드를 작성하였다.

코드

import sys

n = int(sys.stdin.readline())
a = [0] + list(map(int, sys.stdin.readline().split()))
dp = [[0, []] for _ in range(n + 1)]
for i in range(1, n + 1):
    tmp = [0, []]
    for j in range(i):
        if a[j] < a[i]:
            if dp[j][0] > tmp[0]:
                tmp[0] = dp[j][0]
                tmp[1] = dp[j][1]
    # a[i]가 붙을 수 있는 가장 긴 부분 수열에 a[i]를 추가하여 dp[i]에 저장해준다.
    dp[i][0] = tmp[0] + 1
    dp[i][1] = tmp[1] + [a[i]]
dp.sort()
print(dp[-1][0])
print(*dp[-1][1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!