[BOJ_7579] 앱 (python)

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

 

✅ 문제 설명

M바이트의 메모리가 필요하다. 활성화되어있는 앱 A1~AN중에서 몇개를 비활성화해서 M 이상의 메모리를 추가 확보하자. 이 때 비활성화했을 때의 비용의 최소화하여 M이상의 바이트를 확보하자!

✅ 접근 방식

처음에 DP문제인 0-1 knapsack인 것까진 파악을 했다.

근데 왜 못 풀었지..?

음.. 나는 너무 메모리에 대해서만 집중하고 가격에 대해서 for문을 돌 생각을 못했던 것 같다.

---

knapsack[i][j]는 i번째 앱까지 고려했을 때, j비용으로 얻을 수 있는 최대 메모리 값이다.

가로축을 비용, 세로축을 선택지으로 두고, 표의 안쪽을 얻을 수 있는 가치로 기록한다고 생각하면 된다.

 

✅ 코드 설명

import sys

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

앱의 개수 n, 필요한 메모리양 m

그리고 각각의 앱의 메모리양, 비활성화했을 때의 비용을 입력받는다.

앞에 [0] +를 해준이유는 인덱스를 1부터 사용하기 위함이다.

 

knapsack = [[0] * (sum(cost)+1) for _ in range(n+1)]
answer = sum(cost)

knapsack[i][j]는 i번째 앱까지 고려했을 때, j비용으로 얻을 수 있는 최대 메모리 값이다.

answer는 m이상의 메모리양을 얻기 위해 드는 최소 비용을 저장할 값으로, 일단은 cost의 sum(=최댓값)으로 설정해줬다. 

 

for i in range(1, n+1):
    for j in range(0, sum(cost)+1):

앱의 개수만큼 for문을 돌고, 0부터 최대 cost만큼 for문을 돌면서,

i번째 앱까지 고려했을 때, j(0~최대 cost)까지의 비용으로 얻을 수 있는 최대 메모리값을 계산할 것이다.

(*주의! cost는 0부터 시작하므로 j는 1이 아닌, 0부터 시작해줘야한다.)

 

if j < cost[i]:
    knapsack[i][j] = knapsack[i-1][j]
else:
    knapsack[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-cost[i]]+memory[i])

 

만약 i번째 앱의 비용이 비용 j보다 크다면 해당 j비용으로 i앱을 비활성화 시킬 수 없으므로, 크면 이전까지의 값으로 그대로둔다.

만약 그렇지 않는다면, i를 비활성화시켰을 때랑 이전까지의 값중 더 큰 값을 knapsack[i][j]로 지정한다.

 

if knapsack[i][j] >= m:
    answer = min(answer, j)

만약 knapsack[i][j]가 m보다 크면, 목표하던 메모리를 확보한 것이므로 answer이랑 j값을 비교해 더 작은 값으로 초기화한다.

 

✅ 최종 코드

# 앱
# 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법
import sys

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

knapsack = [[0] * (sum(cost)+1) for _ in range(n+1)]
answer = sum(cost)

for i in range(1, n+1):
    for j in range(0, sum(cost)+1):
        if j < cost[i]:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-cost[i]]+memory[i])

        if knapsack[i][j] >= m:
            answer = min(answer, j)

#print(knapsack)
print(answer)

 

✅ 코멘트

- 냅색 문제를 분명 많이 풀어봤다 생각했는데, 이 문제에 대입을 못 시켰다니..! 더 많이 풀어봐야겠다.