백준 9084 - 동전

문제 설명

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 동전 N개가 주어졌을 때 목표를 만들 수 있는 경우의 수를 모두 구하는 것이다.

 

해당 문제는 유명한 dp문제이다.

dp에는 i를 만들 수 있는 경우의 수를 기록할 것이다.

 

그럼 dp에 i를 만드는 수를 기록하는 방법은 i에서 돈을 뺐을 때 경우의 수를 합하여 만들 수 있다.

예를 들어 돈이 1, 2가 있다고 해 보자.

그럼 i를 만드는 방법은 dp[i-1] + dp[i-2]로 만들 수 있다.

물론 1과 2를 여러 번 사용할 수 있기 때문에 이렇게 두 개만 확인하면 안 된다.

따라서 사용할 동전을 정해놓고 해당 동전을 사용해 만들 수 있는 i를 업데이트하면서 진행하면 된다.

dp[0] = 1;

for (auto& coin : coins)
{
    for (int i = coin; i <= target; i++)
    {
        dp[i] += dp[i - coin];
    }
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int T;

int main()
{
    INPUT_OPTIMIZE;

    cin >> T;

    while (T--)
    {
        int N, target;
        cin >> N;

        vector<int> coins;
        vector<int> dp;
        coins.resize(N);

        for (int i = 0; i < N; i++)
        {
            cin >> coins[i];
        }

        cin >> target;
        dp.resize(target + 1, 0);
        dp[0] = 1;

        for (auto& coin : coins)
        {
            for (int i = coin; i <= target; i++)
            {
                dp[i] += dp[i - coin];
            }
        }

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

---