[Python] 백준 7579: 앱

https://www.acmicpc.net/problem/7579

7579번: 앱

	0	1	2	3	4	5	6
	0	0	0	0	0	0	0
(30, 3)	0	0	0	30	30	30	30
(10, 0)
(20, 3)
(35, 5)
(40, 4)

 

	0	1	2	3	4	5	6
	0	0	0	0	0	0	0
(30, 3)	0	0	0	30	30	30	30
(10, 0)	0	10	10	40	40	40	40
(20, 3)
(35, 5)
(40, 4)

 

	0	1	2	3	4	5	6
	0	0	0	0	0	0	0
(30, 3)	0	0	0	30	30	30	30
(10, 0)	0	10	10	40	40	40	40
(20, 3)	0	10	10	40	40	40	60
(35, 5)
(40, 4)

 

	0	1	2	3	4	5	6
	0	0	0	0	0	0	0
(30, 3)	0	0	0	30	30	30	30
(10, 0)	0	10	10	40	40	40	40
(20, 3)	0	10	10	40	40	40	60
(35, 5)	0	10	10	40	40	40	60
(40, 4)

 

	0	1	2	3	4	5	6
	0	0	0	0	0	0	0
(30, 3)	0	0	0	30	30	30	30
(10, 0)	0	10	10	40	40	40	40
(20, 3)	0	10	10	40	40	40	60
(35, 5)	0	10	10	40	40	40	60
(40, 4)	0	10	10	40	40	50	60

1. 냅색 알고리즘으로 푸는 문제이다.

2. 이전 행의 비용을 계속해서 내려주면서 현재값과 (이전의행 - 현재비용) + memory 값을 더해준다.

적은 비용으로 메모리값이 크면클수록 정답이 가까워진다.

n, m = map(int, input().split())
memory = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
length = sum(cost)+1
dp = [[0 for _ in range(length)] for _ in range(n+1)]
ans = 10001

for i in range(1, n+1):
    ci, mi = cost[i], memory[i]
    for j in range(length):
        dp[i][j] = dp[i-1][j]
    for j in range(ci, length):
        dp[i][j] = max(dp[i-1][j-ci] + mi, dp[i][j])
        if dp[i][j] >= m:
            ans = min(ans, j)

print(ans)