[코딩테스트] 백준 12865 평범한 배낭 | C++

문제 12865 평범한 배낭

링크

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

문제 설명

준서는 N개의 물건 (W1, V1), (W2, V2), …, (Wn, Vn)을 가지고 있다.
각 물건은 무게 W와 가치 V를 가지며, 준서의 배낭에는 최대 무게 K까지만 담을 수 있다.

목표는 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 구하는 것이다.

알고리즘 아이디어

문제를 풀기 위해 **DP(동적 계획법)**을 사용한다.

예를 들어 배낭의 용량이 7이라고 해보자.
만약 첫 번째 물건 (6, 13)을 담으면 남은 용량은 1, 총 가치는 13이 된다.
담지 않으면 그대로 용량 7, 가치 0이다.

이때 dp[x]를 용량이 x일 때 얻을 수 있는 최대 가치라고 정의하자.

예를 들어 (6, 13)을 담는 경우,
dp[7]의 후보는 dp[1] + 13이 된다.
하지만 (6, 13)을 담지 않는 경우가 더 클 수도 있으므로, 항상 최댓값을 취한다.

즉, 각 물건을 고려할 때

dp[W] = max(dp[W], dp[W-w] + v)

와 같이 갱신한다. (단, W >= w)

DP 배열 예시

초기:
dp = [0,0,0,0,0,0,0,0] // 인덱스 0..7

(6,13) 처리 (W=7..6)
W=7: dp[7] = max(0, dp[1]+13=13) = 13
W=6: dp[6] = max(0, dp[0]+13=13) = 13
→ dp = [0,0,0,0,0,0,13,13]

(4,8) 처리 (W=7..4)
W=7: dp[7] = max(13, dp[3]+8=8) = 13
W=6: dp[6] = max(13, dp[2]+8=8) = 13
W=5: dp[5] = max(0, dp[1]+8=8) = 8
W=4: dp[4] = max(0, dp[0]+8=8) = 8
→ dp = [0,0,0,0,8,8,13,13]

(3,6) 처리 (W=7..3)
W=7: dp[7] = max(13, dp[4]+6=8+6=14) = 14 ✅
W=6: dp[6] = max(13, dp[3]+6=0+6=6) = 13
W=5: dp[5] = max(8, dp[2]+6=0+6=6) = 8
W=4: dp[4] = max(8, dp[1]+6=0+6=6) = 8
W=3: dp[3] = max(0, dp[0]+6=6) = 6
→ dp = [0,0,0,6,8,8,13,14]

(5,12) 처리 (W=7..5)
W=7: dp[7] = max(14, dp[2]+12=0+12=12) = 14 (유지)
W=6: dp[6] = max(13, dp[1]+12=12) = 13
W=5: dp[5] = max(8, dp[0]+12=12) = 12
→ dp = [0,0,0,6,8,12,13,14]

최종적으로 dp[7] = 14가 답이다.

핵심 포인트

• dp[W] = 용량 W일 때 최대 가치
• 각 물건 (w,v)에 대해 W를 내림차순으로 갱신
  (내림차순으로 돌려야 중복 사용을 방지할 수 있다)
• 최종 정답은 dp[K]

C++ 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> items;
    items.reserve(n);

    for (int i=0; i<n; i++) {
        int w, v;
        cin >> w >> v;
        items.push_back({w, v});
    }

    vector<int> dp(k+1, 0);

    for (auto &p: items) {
        int w = p.first;
        int v = p.second;
        for (int W = k; W >= w; --W) {
            dp[W] = max(dp[W], dp[W-w] + v);
        }
    }

    cout << dp[k] << '\n';
    return 0;
}