[백준] [DP] [이진탐색] 1965. 상자 넣기

1965. 상자 넣기

1965번: 상자넣기

 

• 내 풀이
  • 이진탐색 bisect
  • 뒤에 더 작은 값이 나오면 그 값이 들어갈 수 있는 위치 찾기
  • 더 작은 값으로 바꿔줘야 뒤에 더 많은 숫자들이 들어올 수 있음

#1965
from bisect import bisect_left

n=int(input())
lst=list(map(int,input().split()))

result=[0]
answer=0
for ls in lst:
  if result[-1]<ls:
    result.append(ls)
  else:
    x=bisect_left(result,ls)
    result[x]=ls
    
print(len(result)-1)