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

본문 링크

import sys
input=sys.stdin.readline

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

dp=[0]*N
check=[]
for i in range(N):
    for j in range(i):
        if L[i]>L[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1

K=max(dp)+1
for i in range(-1,-N-1,-1):
    if K-1==dp[i]:
        K=dp[i]
        check.append(L[i])
print(max(dp))
check.reverse()
print(*check)

📌 어떻게 접근할 것인가?

가장 긴 증가하는 부분 수열 알고리즘 이다.

하지만 특이한점은 가장 긴 증가하는 부분 수열을 출력한다는 점이다.
가장 긴 증가하는 부분 수열 2 시리즈의 2번째 문제에서는
$O(Nlog N)$ 으로 문제를 풀었지만 이 풀이방법은 가장 긴 증가하는 부분수열의 길이만 구할수있고
실제로 가장 긴 증가하는 부분 수열의 배열을 구할순없다.

따라서 가장 긴 증가하는 부분 수열 1 이 문제에서 사용한 $O(N^2)$ 의 알고리즘을 활용하고자 한다.

이중반복문으로 $DP$ 테이블을 만들어서 최장길이를 구할때 $DP$ 배열의 변화는 다음과 같다.

여기서 우리는 가장 긴 증가하는 부분수열의 배열을 어떻게 구할것인가?

바로 $DP$ 의 반대편에서 값이 매번 감소하는 지점을 체크 하면 된다.

10 20 10 30 20 50 이라는 리스트가있을때 $DP$ 배열의 결과는
$dp=[1,2,1,3,2,4]$ 이다. 이때 처음으로 감소하는 지점을 체크해보면

4 , 3 , 2 , 1 이고 인덱스 값은 5 , 3 , 1 , 0 이다.
이 인덱스 값을 리스트 값의 인덱스와 비교해보면
L[5]=50 , L[3]=30 , L[1]= 20 , L[0]=10 이다.

역순하면 10 , 20 , 30 , 50 으로 가장 긴 증가하는 부분수열의 배열을 구할수 있다.

따라서 $O(N)$ 의 시간복잡도를 통해 가장 긴 증가하는 부분수열의 배열을 구할수 있다.