[백준] 평범한 배낭

정말 오랫동안 발목을 잡힌 문제..

문제

코드

#include<iostream>
#include<vector>

using namespace std;


int main(){

 	int n, k, w, v;
	cin>>n>>k;
	int dp[n+1][k+1];


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

• 풀이
  
  뭔가 이 문제는 오기가 너무 생겨서 끙끙 앓다가 풀이를 검색해봤었는데, 풀이를 봐도 도저히 혼자 코드를 못 작성했었다. 그리고 오늘도 어김없이 도전했다가 결국 코드를 보았다..

그동안 풀지 못 했던 이유는 너무 간단했다.
점화식 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) 에서
dp[i-1][j-w]+v 을 dp[i][j-w]+v 로 생각하였고, 그래서 i번째 물건을 넣을 때 해당 물건이 반복해서 들어가는 경우를 잡으려고 세상 별 짓을 다 했던 것 같다.

충분히 생각할만도 했던 것 같은데, 중간에 본 풀이에 기억이 사로잡혀서 틀을 벗어나지 못한 것 같다.

다른 dp문제들 처럼 2차원 배열을 구성하고, 물건마다 각각의 무게에서 최댓값을 기록한다.
즉 dp[i][j] 가 의미하는 바는 i번째 물건까지 사용했을 때 무게 j를 채우는 최대 가치이다.

j > i번째 물건의 무게 w라면 i번째 물건을 넣지 않는 경우밖에 없으므로
dp[i][j] = dp[i-1][j], 그게 아니라면 점화식
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)를 이용하여 dp배열을 채워준다.