9084번

9084번 - 동전

D[k][pre] = k 원을 만드는 방법중 이전에 coin[pre]를 쓴 경우의 수.

처음에 그냥 D[k] 로 하면 중복되는 값들이 너무 많이 나왔다. 그래서 pre를 추가 시켜서 문제를 풀 수 있었다.

▼▼▼▼부가설명

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
int n, m;
int coin[21];
long long D[10001][21];
 
long long go(int k, int pre)
{
    if (k < 0)
    {
        return 0;
    }
    if (k == 0)
    {
        return 1;
    }
    if (D[k][pre] >= 0)
    {
        return D[k][pre];
    }
    if (D[k][pre] == -1)
    {
        D[k][pre] = 0;
    }
 
    for (int i = pre; i >= 0; i--)
    {
        D[k][pre] += go(k - coin[i], i);
    }
 
    return D[k][pre];
}
int main()
{
    int tc;
    cin >> tc;
    while (tc--)
    {
        memset(D, -1, sizeof(D));
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> coin[i];
        }
        cin >> m;
 
        cout << go(m, n - 1) << "\n";
    }
 
    return 0;
}