파이썬) 상자넣기 - BOJ

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

1965번: 상자넣기

 

이 문제는 "가장 긴 증가하는 부분 수열2"문제와 똑같은 문제이다.

현재 인덱스 i보다 크면서 인덱스 i에 해당하는 숫자보다 큰 숫자를 찾아야하는 문제이다.

 

from bisect import bisect_left

n = int(input())

arr = list(map(int, input().split()))

dp = []


for i in range(len(arr)):
    if not dp or dp[-1] < arr[i]:
        dp.append(arr[i])
    else:
        dp[bisect_left(dp, arr[i])] = arr[i]

print(len(dp))