Coin Change(COINS) 정답 코드

난이도 ★★★☆☆

문제를 보시려면 여기를 클릭

힌트

전형적인 동적계획법 문제  → 완전 탐색 + 캐시 사용

이하는 코드입니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
 
#define C_MAX 100
#define M_MAX 5000
#define MOD_AMOUNT 1000000007
 
#pragma warning(disable:4996)
 
using namespace std;
 
vector<int> coins;
int cache[M_MAX][C_MAX];
 
int getCount(int money, int maxCoinIndex) {
    int& ret = cache[money][maxCoinIndex];
    if (ret != -1) {
        return ret;
    }
 
    // case found
    if (money == 0) {
        return ret = 1;
    }
 
    // if this is a leaf node
    if (maxCoinIndex == 0) {
        if (money % coins[maxCoinIndex] == 0) {
            return ret = 1;
        }
 
        return ret = 0;
    }
 
    // non-leaf node
    ret = 0;
    for (int pSum = 0; pSum <= money; pSum += coins[maxCoinIndex]) {
        ret = (ret + getCount(money - pSum, maxCoinIndex - 1)) % MOD_AMOUNT;
    }
 
    return ret;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get M, C
        int M, C;
        scanf("%d %d", &M, &C);
 
        // get sorted coins
        coins.clear();
        for (int i = 0; i < C; i++) {
            int coin;
            scanf("%d", &coin);
            coins.push_back(coin);
        }
        sort(coins.begin(), coins.end());
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getCount(M, C - 1));
    }
 
    return 0;
}