[Beakjoon] 7579. 앱

 

🔗 Problem Link

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

---

❔Thinking

• 최소한의 비용으로 M 메모리 만큼을 확보해야 한다 => M 메모리가 확보되었을 경우 중, 최소 비용을 찾는다
• 60의 메모리를 3+3과 0+4로 만들 수 있기 때문에, 무조건 적은 비용으로 계산해나가는 방법을 사용할 수 없다.

---

💻Solution

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
Ms = list(map(int, input().split()))
Cs = list(map(int, input().split()))
datas = [[m,c] for m,c in zip(Ms, Cs)]

answer = 10001
volume = sum(Cs)
bags = [[0]*(volume+1) for _ in range(N+1)]

for i in range(1, N+1):
    w, v = datas[i-1][0], datas[i-1][1]
    for j in range(volume+1):
        if j >= v: # 현재 비용으로 메모리를 추가 확보할 수 있는 경우
            bags[i][j] = max(bags[i-1][j], bags[i-1][j-v]+w)
        else: # 메모리 추가 확보가 불가능한 경우
            bags[i][j] = bags[i-1][j]
        if bags[i][j] >= M:
            answer = min(answer, j)

print(answer)

---

🗝️keypoint

• 분리할 수 없는 (0-1) napsack 문제로 생각하여 풀이할 수 있다.
• 메모리의 합 만큼의 열과 앱의 개수 만큼의 행을 가진 2차원 배열을 통해 문제를 해결한다.
• 예시에서 60 바이트 이상의 메모리를 확보해야 하기 때문에, 60이상의 메모리 중 최소한의 비용을 사용한 경우를 찾아 답으로 반환한다.

예시 풀이