백준 14002: 가장 긴 증가하는 부분수열4 (골드 IV) - DP

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

이 문제는 가장 긴 증가하는 부분수열(11053)문제와 이어집니다. 11053문제는 최대 길이를 출력하는거라면 14002문제는 최대 길이와 함께 그 수열을 출력하는 문제입니다.

해당 문제를 해결하기 위해 아래의 포스팅은 꼭 참고해야합니다. 방법은 이미 아시는 분이라면 넘어가도 좋습니다.

2024.02.27 - [Algorithm/DP(Dynamic Programming)] - 백준 11053: 가장 긴 증가하는 부분수열 (실버 II) - DP

백준 11053: 가장 긴 증가하는 부분수열 (실버 II) - DP

 

솔루션

단순하게 설명하면, DP 리스트의 각 원소가 갱신될 때마다, 그 원소를 갱신하는 데 사용된 j번째 인덱스를 기록하면 됩니다. 예를 들어, DP 리스트의 최대값이 4인 경우, 이는 DP 값이 3인 원소에서 1이 증가했음을 의미하며, 이는 또한 DP 값이 2인 원소에서 1이 증가한 것과, 마찬가지로 1인 원소에서 1이 증가한 것과 연결됩니다. 이는 각 원소의 값을 1씩 증가시켜 리스트를 갱신하는 알고리즘의 특성 때문입니다.

이 말은 새로운 리스트를 선언하고 다시 말해 dp[i] = dp[j] + 1을 할 때의 j값을 i번째 원소에 저장하면 됩니다. 그리고, dp의 값이 1이 될때 까지 반복하여 값을 append한 후, reverse하면 최종 수열이 출력됩니다.

 

소스코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

max_cnt = 0
dp = [1] * N
q = [-1] * N # 최장 길이를 구성하는 요소들의 직전 위치

for i in range(1, N):
    for j in range(0, i):
        if A[i] > A[j]:
            if dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                q[i] = j
                
max_length = max(dp)
max_index = dp.index(max_length)

lis = []
while max_index != -1:
    lis.append(A[max_index])
    max_index = q[max_index]
    
lis.reverse()

print(max(dp))
print(*lis)