[Gold V] 동전 - 9084

[문제 위치]

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

[문제 풀이]

DP 문제이다. 여러 번 반복해서 다른 상황에 대한 DP를 구성해주어야 한다. 그 점을 주의하여 테스트 케이스마다 DP 리스트와 동전의 값을 저장하는 배열을 초기화 해주면 특별할 것은 없다.

#include <iostream>
#include <vector>
#include <algorithm>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main() {
    fastio;
    int T;
    cin >> T;

    while (T--) {
        vector<int> coin_values;
        int DP[10001] = { 0 };
        DP[0] = 1; // 금액 0을 만드는 방법은 1가지

        int N;
        cin >> N;
        for (int j = 0; j < N; j++) {
            int tmp;
            cin >> tmp;
            coin_values.push_back(tmp);
        }

        int goal;
        cin >> goal;

        for (int coin : coin_values) {
            for (int amount = coin; amount <= goal; amount++) {
                DP[amount] += DP[amount - coin];
            }
        }

        cout << DP[goal] << endl;
    }

    return 0;
}