[DP/동적계획법] 백준 1965 상자넣기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1965번: 상자넣기

 

 

 

2. 문제 풀이

 상자의 크기가 나열된 수열이 주어집니다. 이전에 연속적으로 나왔던 작은 상자들은 이후에 나오는 큰 상자에 넣을 수 있습니다. 가장 많이 넣은 상자의 개수를 구해야 합니다.

 

2022.04.13 - [Algorithm] - [DP/동적계획법] 백준 11055 가장 큰 증가 부분 수열 - 파이썬(Python)

[DP/동적계획법] 백준 11055 가장 큰 증가 부분 수열 - 파이썬(Python)

 사실상 '가장 큰 증가 부분 수열'의 길이를 구하는 문제입니다.

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
case = list(map(int, input().split()))

# DP
dp = [1 for _ in range(n)]
for i in range(1, n):
    for j in range(i):
        # 해당 상자가 작으면
        if case[i] > case[j]:
            # 해당 상자를 넣는 게 나은지, 아닌지 판별
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

 문제는 분명 다르지만, 코드는 백준 11055 가장 큰 증가 부분 수열과 똑같습니다.

 DP는 코드 구현이 어렵기 보다는... 문제를 이해하고 캐시를 구성하는 게 중요합니다.