백준/다이나믹 프로그래밍
# 1965 상자넣기
bright_code
2020. 9. 17. 13:44
728x90
반응형
# 가장 긴 증가하는 수열 찾기랑 비슷
n = int(input()) # n <= 1000
data= list(map(int,input().split()))
dp = [1]*1001
for i in range(n):
for j in range(i):
if data[j] < data[i]:
dp[i] = max( dp[j]+1, dp[i])
print(max(dp))
자기 자신인 상자 1 개는 무조건 넣을 수 있으므로 dp = [1]*1001 로 선언한다.
만약 나보다 작은 상자를 발견하면, 해당 상자를 나에게 넣는 것과 넣지 않는 것의 크기를 비교해서 더 큰 것을 넣는다.
https://www.acmicpc.net/problem/1965
1965번: 상자넣기
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 ��
www.acmicpc.net
728x90
반응형