[Python]이분탐색 백준 12015

   문제

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

이전에 봤던 문제이다.

동적계획법에서 봤던 문제이고 조금 고생했던것도 기억이난다.

그때 마음에 걸렸던 시간복잡도O(N^2)인 것도 생각이 나는데 이번에는 이분탐색을 통해

 해결할수 있는것인지 이분탐색 문제에서 N의 크기를 100만으로 키워 다시나왔다.

굉장히 보기쉽게 잘 나와있다.

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

코드는 이전과 크게 다르지 않다.

import sys
 
N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
DP=[0]
 
 
 
for i in range(N):
 
    low=0
    high=len(DP)-1
 
 
    while low<=high:#A[i]보다 작거나 같은수중에 제일 큰거 위치 찾기
        mid=(low+high)//2
        if DP[mid]<A[i]:
            low=mid+1
        else:
            high=mid-1
 
    if low>=len(DP):#위치가 배열보다 크다면 넣어준다
        DP.append(A[i])
    else:#해당 위치의 숫자를 바꿔준다.항상 작거나 같은수를 반환하기때문에 비교하지 않아도된다.
        DP[low]=A[i]
 
print(len(DP)-1)