[python] 백준 12738 가장 긴 증가하는 부분 수열 3

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

12738번: 가장 긴 증가하는 부분 수열 3

 

문제 해결

• 이진 탐색에서 bisect 의 bisect_left를 사용할줄 아는지 문제
• bisect_left(A,num) 은 A 리스트에서 num이상의 수가 최초로 나오는 인덱스를 의미한다.
• 따라서 bisect_left(dp,num)의 값이 k일 때 dp[k] = num으로 바꾸면서 나아가면 가장 긴 증가하는 부분수열을 dp에 넣을 수 있다.

 

CODE

from bisect import bisect_left
n = int(input())
A = list(map(int, input().split()))
dp = []


for num in A:
    k = bisect_left(dp,num)
    if len(dp) == k:
        dp += [num]
    else:
        dp[k] = num
print(len(dp))