백준 - 가장 긴 증가하는 부분 수열5(14003)

시리즈가 꽤 많은 문제다

이게 푼 지 좀 오래돼서 기억이 가물가물하다.

 

 

LIS가 DP로 푸는 방법이 있는데

이 문제는 메모리 제한이 걸리므로

이분탐색으로 풀어주어야 한다.

이분 탐색으로 LIS 길이를 구할 수 있다.

하지만 문제에서는 LIS 요소까지 출력을 해주어야 한다.

 

나는 이분탐색으로 도출한 최장 길이 값을 이용해서

LIS를 역순으로 탐색해서 값을 저장해 주었다.

 

 

def bs_func(target):
    l,r=0,len(bs)
    t = 0
    while l <= r:
        mid = (l+r)//2
        if bs[mid] < target:
            l = mid+1
        else:
            r = mid-1
            t = mid
    return t

n = int(input())
data = list(map(int, input().split()))
lis = [0]*n
lis[0] = 1
bs = [data[0]]
for i in range(1,n):
    if bs[-1] < data[i]:
        bs.append(data[i])
        lis[i] = len(bs)
    else:
        idx = bs_func(data[i])
        bs[idx] = data[i]
        lis[i] = idx+1
max_count = len(bs)
answer_list = []
for i in range(n-1,-1,-1):
    if lis[i] == max_count:
        answer_list.append(data[i])
        max_count -= 1
print(len(bs))
for i in answer_list[::-1]:
    print(i,end=" ")