[Gold V] Coins - 3067

[문제 위치]

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

[문제 풀이]

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T; // 테스트 케이스의 수
    cin >> T;

    while (T--) {
        int N; // 동전의 가지 수
        cin >> N;
        vector<int> coins(N);
        for (int i = 0; i < N; ++i) {
            cin >> coins[i];
        }

        int M; // 만들어야 할 금액
        cin >> M;

        vector<int> dp(M + 1, 0);
        dp[0] = 1; // 0원을 만드는 방법은 1가지 (아무것도 사용하지 않는 것)

        for (int coin : coins) {
            for (int amount = coin; amount <= M; ++amount) {
                dp[amount] += dp[amount - coin];
            }
        }

        cout << dp[M] << endl; // M원을 만드는 모든 방법의 수
    }

    return 0;
}