백준 2294번 동전 2 C++

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

 

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

우리가 원하는 답은 1, 5, 12원의 동전으로 15원을 만들 때 가장 적게 드는 개수를 찾는것이다.

최종 답에서 top - down 방식으로 우선 생각해볼 때 두 가지 경우로 나눌 수 있다.

첫번째는 맨 뒤에 있는 12원의 동전을 포함한 경우이다. 이 경우는 같은 동전을 여러번 사용할 수 있으므로 1, 5, 12원으로 3원을 만드는 작은 문제로 나눌 수 있다. 이때는 12원의 동전을 하나 선택했기 때문에 +1을 해줘야한다.

두 번째는 12원의 동전을 포함하지 않은 경우이다. 이 경우는 1, 5원으로 15원을 만드는 작은 문제로 나눌 수 있다.

이 중 작은 값이 답이 되고, 나눠진 문제에서 같은 방식으로 또 나누면서 문제를 해결할 수 있다.

이 방식으로 구한 점화식은dp[i][j] = min(dp[i][j - v[i]] + 1, dp[i - 1][j]) 이다.

 

dp테이블의 초기값은 dp테이블의 1행은 첫번째 동전만 사용하기때문에 첫번째 동전의 가치로 나누어 떨어질 때만 나누어진 몫으로 채워주었다.

 

#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;

const int bigvalue = 987654321;

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

	int n, k;
	cin >> n >> k;
	vector<int> v(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, bigvalue));
	
	for (int i = 0; i <= n; i++) {
		dp[i][0] = 0;
	}	
	for (int i = 1; i <= k; i++) {
		if (i % v[1] == 0) {
			dp[1][i] = i / v[1];
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j - v[i] < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = min(dp[i][j - v[i]] + 1, dp[i - 1][j]);
			}
		}
	}
	int ans = dp[n][k];
	if (ans == bigvalue) {
		cout << -1;
	}
	else {
		cout << ans;
	}
};