https://www.acmicpc.net/problem/12015
import sys
def binary_search(start, end, a):
global res
if start > end:
return
mid = (end + start) // 2
if stk[mid] < a:
binary_search(mid + 1, end, a)
elif stk[mid] > a:
res = mid
binary_search(start, mid - 1, a)
else:
res = mid
return
n = int(input())
a_list = list(map(int, sys.stdin.readline().split()))
res = 0
stk = [0]
for a in a_list:
if stk[-1] < a:
stk.append(a)
else:
binary_search(1, len(stk) - 1, a)
stk[res] = a
print(len(stk) - 1)나무위키의 도움을 받았다.
https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4
알고리즘은 단순하게 스택 맨 위 원소와 숫자를 비교해서 크면 스택에 넣고, 작으면 스택의 원소 중 본인보다 큰 수들 중 가장 작은 원소에 대입한다. 그 과정에서 이분 탐색이 쓰인다.
이 알고리즘이 왜 항상 예외 없이 정답을 도출하는지 생각하는게 조금 어려웠다. 작은 놈이 스택에 적당한 위치에 치환되는 과정에서는 당연하게 손해보지 않는다. 나중에 방금 치환한 원소를 포함한 LIS가 등장할 수 있기 때문이다. 그렇지만 원소를 치환하는 과정에서 스택의 길이는 짧아지지 않으니 이미 만들어진 LIS의 길이는 보험이 깔려있다.
하지만 길이에만 보험이 깔려있을 뿐 그 뒤에 나오는 수들이 쌓이면서 만들어진 스택은 LIS일 수도, 뒤죽박죽 섞인 수열일 수도 있기 때문에 LIS를 구하려면 다른 방법도 써야 한다.
handsome