백준 11052번 카드 구매하기 C++

출처 : https://www.acmicpc.net/problem/11052

한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다.

카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 수 있다는 것이다.

 

점화식을 세우기 위한 과정을 우선 top-down 방식으로 생각해 보면

이런 식으로 그려볼 수 있다.

설명을 해보자면, 루트는 우리가 최종 구해야 할 답이고,  N개의 카드를 최대한의 가격으로 구매할 때의 가격이다.

왼쪽으로 나눠진 부분은 4번 카드팩을 구매했을때의 상태이다. 4번 카드팩을 구매해서 카드의 개수가 4만큼 줄어들어서 0이 되었고, 카드팩은 구매했다고 사라지는게 아니기 때문에 사용가능한 카드팩은 그대로인 모습이다. 그리고 구매한 카드팩의 가격을 더해준 것이다.

오른쪽으로 나눠진 부분은 4번 카드팩을 구매하지 않았을 때의 상태이다. 4번 카드팩을 구매하지 않았기 때문에 3개의 카드팩 중에서 구매할 수 있고, 구매를 하지 않았기 때문에 카드의 개수는 변화가 없다.

 

왼쪽과 오른쪽 부분에서도 이런 방식으로 계속 타고 내려 갈 것이기 때문에, 둘 중 큰 값을 구하면 그것이 최종 답이 되는 것이다.

그래서 위의 그림에서 나온 점화식은 dp[i][j] = max( dp[i][j-i]+v[i] , dp[i-1][j] ) 이다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> v(n + 1, 0);
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (j - i < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i][j - i] + v[i], dp[i - 1][j]);
			}
		}
	}
	cout << dp[n][n];
};