[백준 12015번] Python - 가장 긴 증가하는 부분 수열 2

가장 긴 증가하는 부분 수열 시리즈는 dp로 계속 풀어왔는데,

이번에 dp로는 시간초과가나서 시간 복잡도가 더 좋은 이분탐색으로 풀었다!

 

원래 start, end 둬서 mid = (start+end)//2 ....이 식 시리즈 몬쥐 알져....

근데 이번엔 bisect_left를 사용해서 풀었는데

넘 간편.... 이해하기도 쉽고 코드도 간편해서 좋았다 😍

 

from bisect import bisect_left
import sys
input = sys.stdin.readline

n = int(input())

arr = list(map(int,input().split()))
dp = [arr[0]]

for i in range(1,n):
    if arr[i]>dp[-1]:
        dp.append(arr[i])
    else:
        dp[bisect_left(dp,arr[i])]=arr[i]
print(len(dp))