[ 백준 / C++ ] 9084 : 동전

[ 문제 ]

 

9084번: 동전 (acmicpc.net)

 

[ 접근방법 ]

 

DP를 활용한다.

 

주어진 코인을 사용하여 금액을 만들 수 있는 방법을 dt 배열에 저장하면서 코인 종류를 하나씩 늘려준다.

 

이 문제는 코인 지급 순서를 구별하지는 않기 때문에 이렇게 코인 종류를 하나씩 늘려주면서 계산을 해주면 된다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int t, n, coin[25], m, dt[10005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> coin[i];
        cin >> m;

        for (int i = 1; i <= m; i++)
            dt[i] = 0;
        dt[0] = 1;

        for (int i = 0; i < n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (j < coin[i])
                    continue;
                dt[j] += dt[j - coin[i]];
            }
        }

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

    return 0;
}