[DP] Python - 7579번, 앱

www.acmicpc.net/problem/7579

7579번: 앱

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
memories = [0] + list(map(int, input().split()))
costs = [0] + list(map(int, input().split()))

costSum = sum(costs)
dp = [[0]*(costSum+1) for _ in range(N+1)]
minCost = costSum

for i in range(1, N+1):
    curMemory = memories[i]
    curCost = costs[i]

    for j in range(1, costSum+1):
        if curCost > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-curCost] + curMemory)

        if dp[i][j] >= M:
            minCost = min(minCost, j)

print(minCost)

 

5 60

30 10 20 35 40

3   0  3   5  4

 

냅색 유형의 문제인 것을 캐치하느냐가 중요하다. 

dp[i][j]는, i번째 앱까지 고려하고, j의 비용까지 고려한 상태에서 확보할 수 있는 메모리의 최댓값이다.

즉, dp[2][3]의 경우는, 1, 2번째 앱만 있으면서, 3의 비용으로 확보할 수 있는 메모리의 최댓값으로, 40이 된다.

 

아래는 예시 케이스에 대한 dp이다.

j가 15까지 있는데, 모든 앱을 실행시킬 때 발생하는 비용이 15이기 때문이다.

 

0~15까지의 비용에 대해 j를 돌리면서, 현재 앱의 비용을 감당할 수 없을 경우에는 바로 위에 있는 경우(dp[i-1][j])를 가져와준다. 이후 j가 현재 앱의 비용을 넘을 경우에는, 위의 경우(dp[i-1][j])와 현재 앱을 켰을 경우(dp[i-1][j-curCost] + curMemory)를 비교하여 큰 값을 넣어준다.

 

이렇게 j에 대해 다 돈 이후에, 만약 현재의 dp가 M 이상 확보했을 경우, 출력하게 될 값(minCost)를 갱신시키되, 최솟값이 들어가게 해준다.

 

여담이지만, 냅색 유형을 모른 채로, 직관적으로 dp를 설계하기란 너무나도 어려운 일이므로, 내키진 않지만 이 유형의 풀이법은 외우다시피 해야할 것 같다.