[백준]12015: 가장 긴 증가하는 부분 순열2

LIS+ 이분탐색

가장 긴 증가하는 부분 순열2

핵심 코드

from bisect import bisect_left
k = bisect_left(stack, lst[i])
		stack[k] = lst[i]

bisect_left(stack, lst[i])
stack lst[i]보다 작은 값 중 가장 큰 값의 인덱스 반환

import sys
from bisect import bisect_left
n = int(input())
lst = list(map(int, input().split()))
stack = [0]
for i in range(len(lst)):
# 스택의 가장 큰 수가 비교하는 수보다 작으면 리스트에 추가
	if stack[-1] < lst[i]:
		stack.append(lst[i])
        # 아니라면 현재 정렬된 stack의 원소중에서 lst[i]가 들어갈 곳의 인덱스 반환
	else:
		k = bisect_left(stack, lst[i])
		stack[k] = lst[i]
print(len(stack[1:]))

이 문제는 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이기 때문에 답이 맞지만 실제로 나오는 답은 가장 긴 증가하는 부분 수열과는 다르다 .
그래서 실제로 증가하는 부분 수열의 원소까지 모두 구하려면 memorization 이 필요하다.