[Baekjoon] 앱(python)

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

문제 접근

최근에 풀었던 평범한 배낭과 똑같은 문제이다.

 

평범한 배낭에서 N개의 물품을 합해서 K만큼의 무게를 확보했던 것과 매칭하면 이 문제에서는 N개의 앱을 합해서 M만큼의 메모리를 확보해야 하는 것이다.

 

단, 이 문제에서는 앱을 비활성화했을 경우의 비용을 최소화하도록 해야 한다.

 

그렇다면 앱들을 비활성화했을 경우의 비용별 최대 메모리 바이트 수를 dp 배열에 저장하여 문제를 풀도록 하면 된다.

---

풀이 과정

dp 점화식은 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])이다.

 

테스트 케이스를 기준으로 모든 앱들을 비활성화할 경우 총 비용은 15이다.

 

dp[N][Cost]	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30
2	0	10	10	40	40	40	40	40	40	40	40	40	40	40	40
3	0	10	10	40	40	40	60	60	60	60	60	60	60	60	60
4	0	10	10	40	40	40	60	60	75	75	75	95	95	95	95
5	0	10	10	40	40	50	60	80	80	80	100	100	115	115	115

 

dp 점화식에 의해 배열을 채우면 위와 같이 앱의 갯수와 비활성화 비용별로 최대로 확보할 수 있는 메모리 바이트 수를 구할 수 있다.

 

테스트케이스에서는 메모리를 60바이트를 확보해야 하므로 dp[N] 배열에서 값이 60이 넘는 것들 중 인덱스가 가장 작은 값을 출력하면 답을 구할 수 있다.

---

정답 코드

"""
    백준 7579번 앱
"""

import sys


N, M = list(map(int, sys.stdin.readline().split()))

memory = [0] + list(map(int, sys.stdin.readline().split()))
cost = [0] + list(map(int, sys.stdin.readline().split()))

total_cost = sum(cost)

dp = [[0] * (total_cost + 1) for _ in range(N + 1)]


for i in range(1, N + 1):
    for j in range(1, total_cost + 1):
        if j < cost[i]:
            dp[i][j] = dp[i - 1][j]
            continue

        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])

for i, m in enumerate(dp[N]):
    if m >= M:
        print(i)
        break