[BOJ/백준] 14002 가장 긴 증가하는 부분 수열 4

N = int(input())
arr = list(map(int,input().split()))
LIS = [arr[0]]
parents = [-1]*N
parents[0] = 0
temp = 0
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        parents[i] = len(LIS)
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]
        parents[i] = idx

LIS_CNT = len(LIS)
result = [-1]*LIS_CNT

for i in range(N-1,-1,-1):
    if parents[i] == LIS_CNT-1:
        result[LIS_CNT-1] = arr[i]
        LIS_CNT -= 1
print(len(result))
print(*result)
    
# https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

    

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기

 

위의 블로그를 참조해서 코드를 풀었다.

 

기본적인 원리는 다음과 같다. LIS를 구하면서 parents라는 배열에 해당 LIS에 들어갔던 idx를 저장해준다.

 

그리고 난뒤 마지막에 LIS의 크기에서부터 하나씩 내려가면서 그에 맞는 배열 값들을 찾아주면 된다.