알고리즘 문제
[백준] 9084번 동전
feelcoding
2020. 3. 14. 18:40
728x90
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int testCase;
cin >> testCase;
for (int t = 0; t < testCase; t++) {
int n, cost;
cin >> n;
vector<int> coin(n);
for (int i = 0; i < n; i++) {
cin >> coin[i];
}
cin >> cost;
vector<vector<int>> dp(n, vector<int>(cost + 1));
for (int i = 0; i <= cost; i++) {
if (i % coin[0] == 0)
dp[0][i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= cost; j++) {
for (int c = 0; c <= j; c += coin[i]) {
dp[i][j] += dp[i - 1][j - c];
}
}
}
cout << dp[n - 1][cost] << '\n';
}
return 0;
}728x90