[백준 12015번] 가장 긴 증가하는 부분 수열 2 (파이썬/python)

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

LIS 문제는 종만북에서 보고 까먹을라 하니까 만나서 복습하는 좋은 기회가 됐다.

DP를 사용하지만 거기에 추가로 탐색절차에 이진탐색(lower bound)를 추가한다.

 

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

생각보다 나무위키에 정리가 잘 돼있다 ㅋㅋㅋ

저기서 2번째 탐색방법을 참고하면 표로 정리되어있어서 보기 좋다

내가 파이썬에서 쓴 bisect_left 함수가 이진탐색의 lower bound 함수이다.

 

 

import sys
from bisect import bisect_left
 
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
 
dp = [arr[0]]
for i in range(n):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect_left(dp, arr[i])
        dp[idx] = arr[i]
 
print(len(dp))