9084번: 동전

https://www.acmicpc.net/problem/9084


$O(tnl)$

knapsack problem과 비슷하게 푼다.

#include<cstdio>
int t, n, m;
int main() {
    scanf("%d", &t);
    while (t--) {
        int dp[10001] = { 1 };
        scanf("%d", &n);
        for (int i = 0, x; i < n; i++) {
            scanf("%d", &x);
            for (int j = x; j <= 10000; j++) dp[j] += dp[j - x];
        }
        scanf("%d", &m);
        printf("%d\n", dp[m]);
    }
    return 0;
}