백준 12865번: 평범한 배낭(C++)

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

코드

#include <iostream>
using namespace std;

int n, k; // 물품의 개수, 준서가 버틸 수 있는 무게
int product[101][2]; // 물건의 무게와 가치 배열
int dp[101][100001];

int max(int a, int b){
	return a >= b ? a : b;
}

void solve(){
	int max_value = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			dp[i][j] = dp[i-1][j];
			if(product[i-1][0] <= j){
				dp[i][j] = max(dp[i][j], product[i-1][1] + dp[i-1][j - product[i-1][0]]);
			}
			max_value = max(max_value, dp[i][j]);
		}
	}
	cout << max_value;
}



int main() {
	cin >> n >> k;
	for(int i=0; i<n; i++){
		cin >> product[i][0] >> product[i][1];
	}
	solve();
}

 

풀이

대표적인 DP문제입니다.

무게 1~K 까지 각각의 무게에서 준서가 들 수 있는 물건 중 최고의 가치를 찾으면 됩니다.

개인적으로 DP문제 풀이를 볼 때 메모이제이션 표가 있으면 이해하는게 편하다 생각하기에 표로 설명드립니다.

문제 예시 입출력을 기반으로 만들어진 표 입니다.

첫번째 행을 보시면 0~7까지의 수가 있습니다.

각각의 값은 들 수 있는 무게입니다.

 

첫번째 열을 보시면 입력받은 물건의 무게와 가치가 있습니다.

 

우선... 처음에는 아무 물건도 안 넣었다고 생각을 해 보겠습니다. 

당연히 들 수 있는 무게가 얼마가 되던 가치는 0이 됩니다.

 

다음으로 첫번째 물건 - 무게가 6이고 가치가 13인 물건을 가방에 넣어볼까요?

무게가 0~5 까지는 물건을 넣을 수도 없기 때문에 동일한 무게에 이전(물건이 없는 경우)물건의 가치를 가져옵니다.

dp[ i ][ j ] = dp[ i-1 ][ j ]

위의 표를 dp라는 2차원 배열이라 가정할 시에는 위와 같은 코드가 되겠습니다.

0을 가져오게 되겠죠.

 

무게가 6이 되는 순간부터는 첫번째 물건을 넣을수가 있게 됩니다. (조건문으로 생각해보기)

 

하지만, 넣을 수 있다고 그냥 넣어버리면 안됩니다.

최대값을 찾아야 겠죠?

최대값은 어떻게 알 수 있을까요?

이 물건을 담았을때 더 들 수있는 무게를 찾고, 그 무게에서 가장 큰 가치를 갖는 경우를 합해주면 됩니다.

빨간색 원으로 한 곳을 생각해보면

현재 들 수 있는 무게는 6 이며

담는 물건의 무게는 6입니다. 따라서 이전 행에서 ... 들수 있는 무게 (6) - 담는 물건의 무게(6) = 0

들 수 있는 무게가 0일때의 가치를 합해줬을 때 그 값이 이전 행의 값보다 큰 경우 교체해 줍니다.

점화식으로 보면

if(product[i-1][0] <= j)

dp[i][j] = max(dp[i][j], product[i-1][1] + dp[i-1][j - product[i-1][0]]);

이와 같이 되겠네요.

 

이러한 점을 잘 생각해서 위와같은 메모이제이션 표를 만든다고 생각하며 풀면 풀 수 있는 문제입니다.