알고리즘
파이썬) 상자넣기 - BOJ
1일1공부실천하자
2023. 12. 5. 22:33
https://www.acmicpc.net/problem/1965
1965번: 상자넣기
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가
www.acmicpc.net
이 문제는 "가장 긴 증가하는 부분 수열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))