[백준] 12865 - 평범한 배낭

12865. 평범한 배낭 풀이

난이도: Gold V
문제 주소: https://www.acmicpc.net/problem/12865

문제 풀이

이 문제는 DP 문제이지만 루프 순서와 기존의 실버 난이도 DP풀던거처럼 풀면 문제가 발생할 수 있는 문제이다.
처음에는 다음 구조로 코드를를 작성했다

vector <pair<int, int >> V;
for (int i = 0; i < n; i++) {
    cin >> w >> v;
    V.push_back(make_pair(w, v));
}
for (int i = 1; i <= k; i++) { 
    for (int j = 0; j < V.size(); j++) { 
        if (i - V[j].first >= 0) {
            dp[i] = max(dp[i], dp[i - V[j].first] + V[j].second);
        }
    }
}

 

이런 구조로 문제를 풀게되면 시간 복잡도는 문제가 없고 예제도 통과를 해서 문제가 없을줄 알았지만 이렇게 풀게 되면 이미 한번 담은 물건을 계속 재사용 하는 문제가 발생한다 이 문제점을 발견하고는 다음 풀이로 변경을했다

for (int i = 0; i < n; i++) {
    cin >> w >> v;
    for (int j = w ; j <= k; j++) {
        dp[j] = max(dp[j], dp[j - w] + v);            
    }
}

 

이번에는 물건을 입력받는 순간에만 dp를 사용하닌까 안일하게 중복이 해결 될거라 생각했고 이번에도 예제를 통과했으니 풀릴줄 알았지만 아직도 한번 담은 물건을 재사용하는 구조를 벗어나지 못하고있었다...

위 처럼 정방향으로 루프를 돌면 dp[j] = max(dp[j], dp[j - w] + v)를 계산할 때 j가 w에서 k로 증가하며 연산이 진행되고 이 과정에서 이미 현재 물건(w, v)이 포함되어 업데이트된 dp[j - w] 값을 뒤쪽의 j가 다시 참조 하게 된다.

예를 들어 무게가 3이고 가치가 10인 물건이 있으면

• j = 3일 때: dp[3] = max(0, dp[0] + 10) = 10
• j = 6일 때: dp[6] = max(0, dp[3] + 10)을 계산하는데 이때 dp[3]은 위에서 이미 10으로 업데이트된 상태다.
• 결국 dp[6] = 20이 되면서 물건이 하나뿐임에도 불구하고 같은 물건을 두 번 담는 오류가 발생한다.

이 문제를 해결 할려면 루프의 방향을 다음과 같이 뒤집어야 한다

for (int i = 0; i < n; i++) {
    cin >> w >> v;
    for (int j = k; j >= w; j--) {
        dp[j] = max(dp[j], dp[j - w] + v);            
    }
}

 

이렇게 역순으로 루프를 돌리면 dp[j]를 계산할때 참조하게 되는 dp[j - w]는 이번물건이 아직 반영되지 않은 값임을 보장할 수 있게 된다

위에서 사용했던 예시 값을 이번 코드에 반영해보면

• j = 6일 때: dp[6] = max(0, dp[3] + 10)을 계산한다. 이때 dp[3]은 아직 0이다.
• j = 3일 때: dp[3] = max(0, dp[0] + 10)을 계산하여 10이 된다.
• 결과적으로 dp[6]과 dp[3] 모두 10이 되어 물건을 중복해서 담지 않고 단 한 번만 사용하게 된다.

예전에도 한번 풀었던 문제인데 오랜만이라 그런가 DP문제를 어떻게 풀어야 했는지 완전히 까먹었던거 같다....
물건을 한번씩만 사용할 수 있을때는 역순 루프를 돌리는 식으로 해결해야함을 기억하자

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <string>
#include <unordered_map>

using namespace std;
int dp[100001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    int w, v;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        for (int j = k ; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);            
        }
    }
    cout << dp[k];
    return 0;
}

'Algorithm > 백준' 카테고리의 다른 글

[백준] 2166 - 다각형의 면적 풀이  (0)	2026.03.22
[백준] 12851 - 숨바꼭질2  (0)	2026.03.19
[백준] 11053 - 가장 긴 증가하는 부분 수열  (0)	2026.03.13
[백준] 1654 - 랜선 자르기  (0)	2026.03.13
[백준] 10989 - 수 정렬하기 3  (0)	2026.03.08