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

 

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

예제 입력  6 10 20 10 30 20 50

예제 출력  4 10 20 30 50

 

풀이

 

가장 긴 증가하는 부분 수열(LIS)의 길이와 그 부분 수열까지 출력하는 문제이다.

LIS의 풀이법은 아래의 포스팅에 있다.

 

[🥈2 / 백준 11053 / 파이썬] 가장 긴 증가하는 부분 수열 (LIS(Longest Increasing Subsequence))

 

LIS를 구하며 dp에 입력받은 숫자의 자리별로 최대 길이가 저장되어 있다.

이제 이것을 가장 큰 것부터 거슬러 올라가며 역으로 부분 수열을 추적한다.

 

가장 최근에 찾은 수보다 1만큼 적은 dp를 찾아가며

현재 dp 인덱스와 일치하는 수열의 수를 따로 저장해두었다가 출력한다.

 

가장 작은 것부터 추적하면 안 되는 이유는

만약 5 4 3 2 1 2 3 라는 숫자를 입력받았을 경우 dp는 1 1 1 1 1 2 3 이 된다.

즉, 답이 5 2 3 으로 출력될 수도 있다는 얘기이다.

 

n = int(input())
nums = [0] + list(map(int,input().split()))
cp,dp = [0,nums[1]],[0,1]

for i in range(2,n+1):
    for j in range(len(cp)-1,-1,-1):
        if nums[i] > cp[j]:
            dp.append(j+1)
            if j+1 < len(cp):
                cp[j+1] = nums[i]
            else:
                cp.append(nums[i])
            break
print(max(dp))

# 역추적
max_idx,ans = max(dp)+1,[]
for i in range(n,0,-1):
    if dp[i] == max_idx-1:
        ans.append(nums[i])
        max_idx = dp[i]
print(*ans[::-1])