[백준] 9084. 동전

컨셉:

int pay(int index, int money)   //coins[0] ~ coins[index]까지의 동전만을 써서 money원을 만들 수 있는 방법의 수

⇒ pay(index, money) = ∑pay(index -1, money - coin[index]로 지불한 금액) 

 

내 코드(정답, 8ms)

 

/**
 * @name    동전
 * @ID      9084
 * @date    2019-08-12
 * @author  Sunmon
 */
 
#include <iostream>
#include <cstring>
 
 
using namespace std;
int N, MONEY;
int coins[20];
int cache[20][10000+1]; 
 
 
//coins[0] ~ coins[index]까지의 동전만을 써서 money원을 만들 수 있는 방법의 수 리턴
int pay(int index, int money)
{
 
    //base case
    if(money <= 0) return (money == 0);
    if(index <  0) return 0; 
 
    int& ret = cache[index][money];
    if(ret != -1) return ret;
    if(index == 0) return ret =  (money % coins[index] == 0);
 
    int amount = 0;     //coins[index]로 지불하는 금액
    ret = 0;            //지불하는 방법의 수
    while(amount <= money)
    {
        ret += pay(index-1, money-amount);
        amount += coins[index];
    }
 
    return ret;
}
 
 
int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        cin >> N;
        memset(cache, -1, sizeof(cache));
        for(int i = 0; i< N; i++) cin >> coins[i];
        cin >> MONEY;
        cout << pay(N-1, MONEY) << endl;
 
    }
}