3067 Coins

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

d[i] = 주어진 동전으로 i원을 만드는 경우의 수

오름차순으로 주어진 동전의 경우의 수를 차례대로 추가해가면 중복없이 테이블을 채울 수 있다.

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