3067번 Coins

 

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

 

 

냅색

 

 

#include<bits/stdc++.h>

using namespace std;

int N, T, cache[10001][21];
vector<int> v;

int ks(int goal, int idx)
{
    if (idx == N) {
        if (goal == 0) return 1;
        return 0;
    }

    int& ret = cache[goal][idx];

    if (ret != -1) return ret;

    ret = ks(goal, idx + 1);
    if (goal - v[idx] >= 0) {
        ret += max(ks(goal - v[idx], idx), ks(goal - v[idx], idx + 1));
    }

    return ret;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);


    scanf("%d", &T);

    while (T--)
    {
        v.clear();
        memset(cache, -1, sizeof(cache));

        scanf("%d", &N);

        int coin;
        for (int i = 0; i < N; i++) {
            scanf("%d", &coin);
            v.push_back(coin);
        }

        int total;
        scanf("%d", &total);

        printf("%d\n", ks(total, 0));
    }

    return 0;
}