[백준] 14003: 가장 긴 증가하는 부분 수열 5

이분탐색 + memorization

가장 긴 증가하는 부분 수열 5

이 문제와 가장 긴 증가하는 부분 수열 4 다른 점은 수의 범위이다.
가장 긴 증가하는 부분 수열 4는 크기가 1000이고 범위가 1000이기 때문에 O(n^2)으로 가능하지만 이 문제는 시간 초과가 난다. 그래서 가장 긴 증가하는 부분 수열 3 처럼 접근한 뒤 memorization 이 필요하다.

import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
lst =  list(map(int, input().split()))
stack = [-1000000001]
# 부분 수열의 길이 정보를 저장할 리스트 
d = [0] * n
maxVal = 0
for i in range(len(lst)):
	if stack[-1] < lst[i]:
		stack.append(lst[i])
        	# 가장 긴 부분 수열이 완성
		d[i] = len(stack)-1
        	# 최댓값 갱신
		maxVal = d[i]
	else:
    		#현재까지의 가장 긴 부분 수열
		d[i] = bisect_left(stack, lst[i])
        	# 스택 갱신
		stack[d[i]] = lst[i]

print(d)
res = []
# max 값 줄여가면서 부분 수열 갱신
for i in range(len(d)-1, -1, -1):
	if maxVal == d[i]:
		res.append(lst[i])
		maxVal -= 1

res.reverse()
print(*res)