백준 9084번 동전 C++

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

 

dp로 해결할 수 있는 문제이다. 배낭 채우기 문제와 비슷하다.

dp[n+1][m+1]배열을 만들었다. dp[i][j]의 의미는 i번 동전까지 사용해서 j원을 만들 수 있는 경우의 수 라고 정하였다.

동전 몇개로든 0원은 언제나 만들 수 있어서 dp[i][0]은 모두 1로 초기화 해주었다.

 

i번째 동전까지 사용해서 j원을 만들 수 있는 경우는

1) i-1번째 동전까지 사용하고 j원을 만든 상태에서 아무 행동도 하지 않는 경우와

2) i번째 동전까지 사용했는데 j-coins[i]원을 만든 상태에서 coins[i]를 추가해서 j원을 만드는 경우가 있다.

따라서 점화식은 dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 로 세우고 문제를 해결하였다.

 

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

using namespace std;
using ll = long long;

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

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n;
		vector<int> coins(n + 1, 0);
		for (int i = 1; i <= n; i++) {
			cin >> coins[i];
		}
		cin >> m;
		vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
		for (int i = 0; i <= n; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				int a = dp[i - 1][j];
				int b = 0;
				if (j - coins[i] >= 0) {
					b = dp[i][j - coins[i]];
				}
				dp[i][j] = a + b;
			}
		}
		cout << dp[n][m] << "\n";
	}
};