[백준(BOJ)] 9084번 동전 C++

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

9084번: 동전

 

어떤 문제인가?

https://codegarden-farmjun.tistory.com/55

[백준(BOJ)] 2293번 동전1 C++

동전1 문제와 똑같은 문제이다.

다만 다른 점은 이 문제는 테스트케이스가 여러개 존재한다.

이 부분만 처리해주면 된다.

 

#include "iostream"

using namespace std;

int dp[10001];

int main(){

    int t;
    cin >> t;

    for(int i=0; i<t;i++){
        fill(dp, dp+10001, 0);

        int n, m;
        cin >> n;

        int coin[n];

        for(int j=0;j<n;j++){
            cin >> coin[j];
        }
        cin >> m;

        dp[0] = 1;

        for (int j = 0; j < n; j++) {
            for (int k= coin[j]; k <= m; k++) {
                dp[k] += dp[k - coin[j]];
            }
        }

        cout << dp[m] << "\n";
        
    }
}