[백준][Python] 12738 LIS3

LIS는 예전에는 dp를 통해 이전값들을 검사해주며 모든 count를 계산해 풀었다면

이제는 이진탐색으로 직접dp수열을 관리하며 들어가야할 자리를 찾고 나보다 큰수는 나로 교체해주는 식으로 진행된다.

물론 내가 제일 크다면 그냥 오른쪽에 append한다.

이렇게하면 최종 dp에 남는 수열은 LIS는 안되지만 그 길이는 lis의 길이이다.

알고리즘은 의외로 heap을쓰는 회의실 배정문제와 비슷한 편.

from bisect import bisect_left #이진탐색 코드, 같은 수일 경우 왼쪽 index를 돌려준다

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

for i in A:
    k = bisect_left(dp, i) #자신이 들어갈 위치 k
    if len(dp) <= k: #i가 가장 큰 숫자라면
        dp.append(i)
    else:
        dp[k] = i #자신보다 큰 수 중 최솟값과 대체
print(len(dp))