[백준] 9084번 동전 C++

문제 출처: https://www.acmicpc.net/problem/9084

9084번: 동전

coin(현재 사용할 동전 idx, 만들어야 하는 값) 함수를 구현하여 탑다운 방식으로 풀었다.

coin(idx , value) = coin(idx+1, value) + coin(idx+1, value - 1*arr[idx]) + coin(idx+1 , value - 2*arr[idx]) + ...

의 점화식을 세울 수 있다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

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

int coin(int idx, int nowVal) {
    if (idx == N) {
        if (nowVal == 0)return 1;
        else return 0;
    }
    if (dp[idx][nowVal] != -1)return dp[idx][nowVal];

    int val = 0;
    for (int i = 0; i < 10001; i++) {
        if (nowVal - arr[idx] * i >= 0)val += coin(idx + 1, nowVal - arr[idx] * i);
        else break;
    }
    
    return dp[idx][nowVal] = val;

}


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int T; cin >> T;


    while (T--) {
        fill(&dp[0][0], &dp[20][10001], -1);
        cin >> N;
        for (int i = 0; i < N; i++)cin >> arr[i];
        cin >> M;
        cout << coin(0, M)<<'\n';
    }


}