난이도 : 골드 3
유형 : DP 심화
https://www.acmicpc.net/problem/7579

---

문제 요약

목표:

• N개의 앱이 있음. 각각의 앱은 메모리를 차지하고 있고, 앱을 비활성화하면 일정한 비용이 든다.

최소의 비용으로 M 바이트 이상의 메모리를 확보하고 싶다.

입력:

• 첫째 줄:
  - N (앱의 개수, ≤ 100)
  - M (확보해야 하는 메모리, ≤ 10,000)

• 둘째 줄: 각 앱이 차지하는 메모리 (N개)

• 셋째 줄: 각 앱을 비활성화할 때 드는 비용 (N개, 각 비용 ≤ 100)

출력:

• M 바이트 이상을 확보할 수 있는 최소 비용을 출력

아이디어 흐름

“얘는 뭔가 ‘최소 비용’으로 ‘가치’를 얻는 문제 같네 → 냅색 문제네?”

“어떤 게 가치고 어떤 게 비용일까?”
→ 메모리는 얻는 값(value), 비활성화 비용은 무게(weight)

“dp 배열을 비용 기준으로 잡으면 되겠다. 비용으로 얻을 수 있는 최대 메모리 저장”

“0/1 냅색은 반드시 역순으로 순회해야 중복 선택을 막지”

“이제 dp[cost] >= M인 것 중에서 cost가 제일 작은 애 출력하면 되겠다”

“0/1 냅색은 반드시 역순으로 순회해야 중복 선택을 막지”

이것은 냅색 문제의 여러 유형이 있는데 각 아이템을 한 번만 선택할 수 있는 0/1 냅색 문제에 사용하는 기법이다.

아래 코드를

for j in range(cost, max_cost + 1):
    dp[j] = max(dp[j], dp[j - cost] + mem)

이렇게 순방향으로 dp를 설정하면
cost = 3, memory = 30 라고 할 때,
dp = [0,0,0,0,0,0,0]

j = 3 → dp[3] = max(dp[3], dp[0] + 30) → dp[3] = 30
j = 6 → dp[6] = max(dp[6], dp[3] + 30) → dp[6] = 60
이렇게 dp[3]이 중복 사용 되어 dp[6]이 60이 되는 문제가 발생한다.

그러나

for j in range(max_cost, cost - 1, -1):
    dp[j] = max(dp[j], dp[j - cost] + mem)

이렇게 역순으로 돌면

j = 6 → dp[6] = max(dp[6], dp[3] + 30) → 아직 dp[3]은 0 → dp[6] = 30
j = 3 → dp[3] = max(dp[3], dp[0] + 30) → dp[3] = 30

이렇게 중복 사용을 막을 수 있ㄷ다.

해답 및 풀이

import sys
input = sys.stdin.readline

# 입력
N, target_memory = map(int,input().split())
memories = list(map(int,input().split()))
costs = list(map(int,input().split()))

max_cost = sum(costs)

dp = [0] * (max_cost + 1)
# dp[cost] = cost만큼 비용을 썼을 때 얻을 수 있는 최대 메모리

for i in range(N):
    memory = memories[i]
    cost = costs[i]

    # 비용이 큰 역순으로 돌아야 같은 앱을 여러 번 선택하지 않게 된다.
    for j in range(max_cost, cost -1, -1):
        # 기존에 j - cost 비용으로 확보했던 메모리에 현재 앱 메모리를 더한 값과,
        # 이 앱을 선택하고, 남은 비용(j - cost)으로 만들 수 있었던 최대 메모리에 현재 앱의 memory를 추가한다.
        dp[j] = max(dp[j], dp[j - cost] + memory)

# 목표: dp[cost] >= target_memory 가 되는 가장 작은 cost 값 찾기

for cost in range(max_cost + 1):
    if dp[cost] >= target_memory:
        print(cost)
        break

---

냅색 문제 꽤나 까다롭고 유형도 여러개인 것 같아 한번 정리가 필요해 보인다.

유형	설명	아이템 선택 방식	dp 테이블 기준	예시 문제
0/1 Knapsack	각 아이템을 한 번만 선택	❌ 중복 불가	dp[무게] 또는 dp[비용]	백준 12865
Unbounded Knapsack	각 아이템을 여러 번 선택 가능 (무제한)	✅ 중복 가능	dp[무게]	백준 2294
Bounded Knapsack	각 아이템마다 사용 횟수 제한	❌ 중복 제한 (개수 존재)	dp[무게]	백준 7579 (cost가 weight 역할)
Subset Sum	주어진 숫자들로 어떤 합이 가능한가?	각 수를 한 번씩만 사용	dp[합] → 가능 여부	백준 1182 (부분수열 합)
Multi-dimensional Knapsack	두 개 이상의 제약이 존재 (무게+부피 등)	상황에 따라 다름	dp[무게][부피] 등 다차원	고난이도 문제들 (ex. ACM-ICPC)