BOJ 9084 동전

 

문제 링크 : https://www.acmicpc.net/problem/9084

9084번: 동전

 

동전의 종류 N 이고 만들어야 할 금액은 V 이다.

$recur(n,v)$ 는 $n \; (1\le n \le N)$ 번 이하의 동전들을 사용해서 v 금액을 만드는 방법의 수이다.

 

#include<bits/stdc++.h>

using namespace std;

int N,V;
int arr[21];
int dp[21][10001];

int recur(int n, int v){
    if(n==1){
        if(v%arr[1]==0) return 1;
        else return 0;
    }
    
    int &ret=dp[n][v];
    if(ret) return ret;
    
    int q=v/arr[n];
    for(int i=q;i>=0;i--)
        ret+=recur(n-1,v-arr[n]*i);
    
    return ret;
}

void solve(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&arr[i]);
    
    scanf("%d",&V);
    memset(dp, 0, sizeof dp);
    
    printf("%d\n",recur(N, V));
}

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