백준[9084] 동전

문제 설명

문제 링크

http://icpc.me/9084

9084번: 동전

풀이

dp로 풀이할 수 있다.

dp정의는 dp[남은 돈][몇 번째 동전까지 썼는지]로 정의할 수 있다.

코드

#include <cstdio>
#include <cstring>

int dp[10004][22], arr[10004], n;


int dpf(int money, int coin_idx) {
    int &ret = dp[money][coin_idx];
    if (ret) return ret;
    if (!money) return 1;
    for (int i = coin_idx; i < n; i++) {
        if (money - arr[i] >= 0) ret += dpf(money - arr[i], i);
    }
    return ret;
}

void solve() {
    memset(dp, 0, sizeof dp);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int m; scanf("%d", &m);
    printf("%d\n", dpf(m, 0));    
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}