[백준 7579] 앱 (python)

7579번: 앱

---

DP를 사용하는 Knapsack Problem이다.

 

1. 각 앱의 메모리들을 memory 배열에 저장한다.
2. 각 앱의 활성화 추가 비용들을 cost 배열에 저장한다.
3. 각 행은 앱을 나타내고, 열은 비용을 나타내는 dp배열을 생성한다. (최고비용이 모든 앱의 합이므로 sum(cost)+1을 열 개수로 설정)
4. 비용(j)이 cost보다 작다면 이전의 값(dp[i-1])을 가져온다.
5. 비용(j)이 cost보다 크다면 해당 cost와 함께 비용(j)를 만들수 있는 값(dp[j-cost])에 해당앱의 메모리를 추가한 값과, 이전 앱까지의 값(dp[i-1]) 중 큰값을 선택한다.
6. 값이 확보할 메모리 M보다 크다면 _min 값을 j로 초기화 한다.

 

import sys
input = sys.stdin.readline


N, M = map(int, input().split())
memory = list(map(int, input().split()))
cost = list(map(int, input().split()))

max_cost = (sum(cost)+1)
dp = [[0]*max_cost for _ in range(N+1)]
_min = max_cost
for i in range(1, N+1):
    for j in range(len(dp[0])):
        if j < cost[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i-1]] + memory[i-1])
        if dp[i][j] >= M and _min > j:
            _min = j

print(_min)