problem-12015

과정
처음에 dp를 이용해서 풀었을 때 시간초과로 안됨
-> 이분탐색 이용
1. i부터 n까지 for문 안에서
2. 만약 a[i]값이 result의 마지막값(제일큰값)보다 크면 그대로 result에 추가
3. 작으면 bisect모듈을 이용하여 들어갈만한 곳에 있는 값과 대치

3-1. 이렇게 하는 이유는 작은 수로 대치하면 그 다음에 다른 수가 왔을 때 추가할 수 있는 확률이 높아짐
3-2. 만약 리스트를 그대로 출력하라고 하면 이런 방식으로는 하면 안됨, 길이만을 구할때 유효함.

import sys
input=sys.stdin.readline
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))

result=[]

for i in range(n):
    if not result:
        result.append(a[i])
    else:
        if a[i]>result[-1]:
            result.append(a[i])
        else:
            index=bisect_left(result,a[i])
            result[index]=a[i]
    
print(len(result))

ps. bisect모듈을 이용하지 않고 직접 bi_search를 만들어서 풀어봤는데 계속 틀렸다. 다음에 다시 시도해봐야할 것 같다.

time:60분
resolved:x