[백준]9084 동전

 

문제

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

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

입력

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

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

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

 

골드5 DP문제입니다.

n 종의 동전으로 m원을 만드는 경우의 수를 찾는 문제입니다

	#include<bits/stdc++.h>
	
	using namespace std;
	
	int arr[21][10001];
	vector<int>coins;
	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);

		int t, n, x, m;
		cin >> t;
		while (t > 0) {
			coins.clear();
			memset(arr, 0, sizeof(arr));
			cin >> n;
			for (int i = 0; i < n; i++) {
				cin >> x;
				coins.push_back(x);
			}
			cin >> m;
			for (int i = 0; i < coins.size(); i++) {
				if (i == 0) {
					for (int j = 1; j <= m; j++) {
						j% coins[i] == 0 ? arr[i][j] =1 : arr[i][j] = 0;
					}
				}
				else {
					for (int j = 1; j <= m; j++) {
						//i번째코인만사용, j원만들기

						if (j % coins[i] == 0)
							arr[i][j]++;
						for (int k = 0; k <= j / coins[i]; k++) {
							arr[i][j] += arr[i - 1][j - coins[i] * k];
						}

					}
				}
			}
			cout << arr[n-1][m] << "\n";
			t--;
		}
		
	}

arr[i][j]는 0~i까지의 동전만 사용해서 j원을 만드는 경우의 수입니다.

따라서 arr[0][j]에서는 0또는 1을 저장하고,

그 이후부터는 i번째 coin을 0개부터 k=j/coins[i]개 까지 사용할 때까지

arr[i-1][j - coins[i]*k]를 더해줍니다.

 

이때 coins[i]만으로 m원을 만들 수 있는경우 ( j%coins[i]==0)

1을 더합니다.