실습 2주차 [3] Coin Combination

문제

여러 종류의 동전이 있어서 그 동전들을 이용해서 특정한 금액을 만드려고 한다.

처음에 coin 종류의 개수를 입력 받고, 그 다음에는 각 동전마다의 액면가를 입력 받으며, 마지막으로 원하는 가격을 입력한다.

출력해야 할 값은 그 가격을 만들 수 있는 동전의 조합의 개수이다.

여기서 동전의 종류의 개수는 최대 10개까지만 입력한다고 가정하자.

입력 형식

{동전 종류 수}

동전1 동전2 동전3 ... 동전n

{원하는 가격}

Hint : Recursion으로 구현하도록 한다. (Dynamic Programming으로 구현하면 좀 더 빠르게 할 수 있다.)

답안

#include <iostream>

using namespace std;

int counting_coin(int[], int, int, int);

int main(){
	int coin[10];
	int n, sum;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> coin[i];
	cin >> sum;
	cout << counting_coin(coin, 0, n - 1, sum);
	return 0;
}

int counting_coin(int coins[], int idx, int max_idx, int sum){
	if (idx > max_idx)
		return 0;
	if (sum == 0)
		return 1;
	if (sum < 0)
		return 0;
	return counting_coin(coins, idx, max_idx, sum - coins[idx]) + counting_coin(coins, idx + 1, max_idx, sum);
}

+ counting_coin 함수는 coins 배열에서 idx부터 max_idx에서의 coin으로만 sum 값을 만들 수 있는 개수를 출력하는 함수이다.

이 알고리즘을 잘 살펴보면 sub-problem이 overlapping이 된다는 것을 알 수 있고, 이를 통해서 Dynamic Programming으로 구현하면 좀 더 빠르게 만들 수 있다는 것을 알 수 있다.