[BOJ] 14003. 가장 긴 증가하는 부분 수열 5 (Python)

14003번: 가장 긴 증가하는 부분 수열 5

 

가장 긴 증가하는 부분 수열을 DP로 구하는 방법은 저번에 설명했었다.

이번에는 Lower Bound를 통해서 구하는 방법에 대해 설명하겠다.

 

먼저 배열 내에서 가장 긴 증가하는 부분 수열의 길이를 구하고자 할 때 첫 번째 숫자부터 순서대로 확인해보면 된다.

이때

1. 현재까지 구한 LIS의 마지막 값보다 더 크면 그냥 값을 이어 붙이면 된다.

2. 현재까지 구한 LIS의 마지막 값보다 작으면 LIS 내에서의 Lower Bound 위치를 찾는다.

 

Lower Bound를 찾아 값을 바꿔주는 이유는 최장 증가 수열을 구하기 위해서는 배열을 구성하는 값이 작을 때에 더 긴 수열을 찾을 수 있기 때문!

 

근데 이 문제에서는 단순히 길이 뿐만 아니라 최장 증가수열이 무슨 숫자로 구성되어있는지까지 출력을 해야한다.

따라서 각각 숫자들이 들어갈 수 있는 index를 따로 저장하는 방법을 썼다. (memoization)

 

 

from bisect import bisect_left
from copy import deepcopy

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

lst = [a[0]]
memoization = [0 for _ in range(n)]

for idx, num in enumerate(a[1:], start = 1) :
    if lst[-1] < num :
        lst.append(num)
        memoization[idx] = len(lst)-1
    else :
        b_idx = bisect_left(lst, num)
        lst[b_idx] = num
        memoization[idx] = b_idx


maxVal = len(lst)
print(maxVal)
answer = []
maxVal -= 1
for idx in range(n-1, -1, -1) :
    if memoization[idx] == maxVal :
        answer.append(a[idx])
        maxVal -= 1
answer.reverse()
print(* answer)