개발/알고리즘
백준 - 가장 긴 증가하는 부분 수열5(14003)
Seongjun_You
2023. 12. 12. 20:28
시리즈가 꽤 많은 문제다
이게 푼 지 좀 오래돼서 기억이 가물가물하다.
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=" ")