[백준/c++] - 12865 평범한 배낭

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

12865번: 평범한 배낭

 

 

 

 유명한 DP문제이다. DP문제를 푼지 너무 오래되어서 다시 풀어봤는데, 다시 봐도 점화식을 떠올려내기 쉽지않다.

 

 

 

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

struct Thing {
	int W;
	int K;
};

int dp[101][100001]{ 0, }; // i개까지 고려했을 때 j무게 제한 기준 최대 가치

int limitW = 0;
int N;


vector<Thing> things;

// 무게순 오름차순 정렬
bool compare(Thing a, Thing b) {
	return a.W < b.W;
}


// dp[i][j] -> i번 물건까지 고려했을때, j의 무게제한에서 가장 큰 가치

void memoization() {

	// 가장 가벼운 무게의 물건부터 시작
	for (int i = 1; i <= N; i++) {

		for (int j = 1; j <= limitW; j++) {
			Thing thing = things[i];

			if (j >= thing.W) { // 물건을 담을 수 있을 때
				dp[i][j] = max(dp[i - 1][j - thing.W] + thing.K, dp[i - 1][j]);
			}
			else { // 물건을 담을 수 없을 때
				dp[i][j] = dp[i - 1][j];
			}
		}

	}

}


void input() {
	
	cin >> N >> limitW;

	// 0번 더미
	things.push_back(Thing{ 0, 0 });
	
	for (int i = 0; i < N; i++) {
		int W, K;
		cin >> W >> K;
		things.push_back(Thing{ W, K });
	}

	sort(things.begin(), things.end(), compare);

}


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

	input();
	memoization();
	
	cout << dp[N][limitW];
}

 

 

 

 작성한 전체 코드이다. 인터넷에 흔히 돌아다니는 정답 코드들과 다를 것은 없다. 유의해야할 점은 dp를 2차원 배열을 이용하여 풀어야한다는 것이다. 처음에는 1차원 배열을 이용해서 dp[n]을 무게 n일때의 최대가치로 설정하고 풀이를 시도하였는데 바로 틀렸다. 2차원 배열을 사용하는 이유를 곰곰이 생각해 보면 고려해야할 요소가 2가지 라서 그렇다.

 

 

 

 

 만약 이 문제가 물건의 가치가 모두 동일하고 물건을 정해진 순서대로만 넣어야하는 문제였다면 내가 생각한대로 dp[n]을 이용하여 풀이가 가능했을 것이다. 하지만 이 문제는 모든 물건의 가치가 다르고 어떤 물건을 먼저 선택하여 넣던 상관이 없기 때문에 1차원 배열로는 풀이가 어렵다.

 

 

 

 

 정답코드에서 dp[i][j]는 i번째 물건까지 고려했을 때 j의 무게 제한에서 가질 수 있는 최대 가치이다. 2중 반복문에서 바깥쪽은 물건의 개수만큼, 안쪽은 0의 무게에서 무게제한 무게까지 반복문을 돌며 dp를 갱신한다. 

 

 

 

 

 특히 기억해야 할 것은 바깥쪽 반복문에 고려할 물건의 번호를 둠으로써 무게를 갱신하면서 몇번 물건까지 고려한 결과인지를 기록하기 쉽게 해 놓았다는 것이다.

 

 

 

 

 만약 다음에도 dp문제를 만났는데 풀이가 좀처럼 안될 경우 2차원 배열을 통해 좀더 자세히 dp를 수행할 수 있도록 해야겠다.