[백준] 3067 Coins

 

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N 가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작다고 가정해도 된다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

 

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int dp[10001], tc, a, b, x;
vi coin;
int main() {
	FAST;
	cin >> tc;
	while (tc--) {
		coin.clear();
		mset(dp);
		int n, t;
		cin >> n;
		rep(i, n) {
			cin >> x;
			coin.push_back(x);
		}
		dp[0] = 1;
		cin >> t;
		for (auto c : coin) {
			for (int i = c; i <= t; i++) {
				dp[i] += dp[i - c];
			}
		}
		cout << dp[t] << "\n";
	}
}

dp 문제입니다

1부터 t 원까지 만드는 경우의 수를 구해야합니다.

a,b,c 동전까지 사용했다고 하고 d 동전을 사용해야할때

a,b,c,d동전까지 사용할때 k원을 만드는 경우는 dp[k]+dp[k-d] 입니다.

a,b,c동전까지 사용한 경우에, d동전을 하나 써서 만들 수 있는 경우를 더하는겁니다.

1차원 배열로 해결할 수 있습니다.