[백준] 12865번: 평범한 배낭 풀이 및 해설(C++)

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

12865번: 평범한 배낭

 

풀이

소위 냅색문제라고 불리는 문제이다.

2차원 배열을 사용해서 풀면 된다. 

열은 무게를, 행은 몇 번째 물건까지 넣었는지 표시하고, 테이블의 각 자리에 가치를 저장한다.

냅색문제에서 물건을 대할때 선택지는 2가지다. 물건을 넣던가 혹은 그렇지 않던가.

1. 그래서 물건을 넣지 않을 거면 이전 행에서 그대로 할당받고

2. 물건을 넣을 것이면  (현재의 열(무게)-현재 넣을 물건의 무게)에 가치를 할당한다.

위의 둘을 비교해 큰 것을 고르면 된다.

 

 

해답 코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    long long n,limit,weight,value;
    cin>>n>>limit;
    long long arr[n][limit+1]={0};
    cin>>weight>>value;
    for(int i=0; i<weight; i++){
        arr[0][i]=0;
    }
    for(int i=weight; i<limit+1; i++){
        arr[0][i]=value;
    }
    //첫 행의 물건 무게보다 작은 열에는 0, 물건 무게보다 큰열에는 가치를 넣는다.
    //첫 행에는 점화식을 사용할 수 없으므로 다음과 같이 할당한다.     
    for(int j=1; j<n; j++){
        cin>>weight>>value;
        for(int i=0; i<limit+1; i++){
            arr[j][i]=arr[j-1][i];
            //일단 모든 행의 값을 이전 행에서 할당받는다.
        }
        for(int i=0; i+weight<limit+1; i++){
            if(arr[j-1][i+weight]<arr[j-1][i]+value){
                arr[j][i+weight]=arr[j-1][i]+value;
                //이번에 넣을지 말지 정할 물건의 넣었을때 가치와(arr[j-1][i]+value)
                //넣지 않았을때의 가치 (arr[j-1][i+weight])를 비교해 큰 값을 할당한다.
            }
        }
        
    }
    cout<<arr[n-1][limit];
    
    return 0;
}

해맸던 부분

입력으로 주어지는 변수들은 배열에 한 축으로 적용해야겠다고 생각하기 쉬우나 명시적으로 주어지지 않는 변수들은 생각하기 어렵다. 이 문제에서는 몇 번째까지 물건을 넣었는가를 한 축으로 적용해야 한다는 사실을 상상하기 어려웠다. 

 

그리고 이전에 푼 풀이에서 배열내에서 따로 최댓값을 구하는 if문이 있어 없앴다. 그 당시에는 마지막 열과 행의 끝이 곧 최댓값이 된다고 제대로 이해하지 못한 것 같다.

 

풀이 방법을 듣기 전에는 어려우나 한번 들으면 왜 몰랐지 싶은 그런 문제인 것 같다.

 

PLUS

여기서는 2차원 배열을 썼지만 1차원 배열을 써서 해결할 수도 있다.

비슷한 방법이지만 몇번째 물건까지 넣었는지 확인하는 index 행을 없애고, 큰 무게부터 역순으로 넣으면 된다.