[백준 C++] 2624번 동전 바꾸기

2624번: 동전 바꿔주기

문제 요약

문제

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10×2
• 20 = 10×1 + 5×2
• 20 = 10×1 + 5×1 + 1×5
• 20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에는 지폐의 금액 T(0＜T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0＜k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi ≤ T)와 개수 ni(0＜ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.
• 출력: 첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다. ``` 예제1

입력 20 3 5 3 10 2 1 5 출력 4

## 풀이
하나의 동전 종류부터 차례대로 진행한다. 총 금액에서 역순으로 간다. 현재 금액에서 현재 동전 금액을 한개부터 최대 개수까지 빼가면서 그 뺀 금액 dp에 값이 있으면 현재 금액 dp에 더한다. 역순으로 가는 이유는 정방향으로 갈 경우 개수 새기가 애매해지기 때문이다. 5원짜리 동전이 1개 있다고 치면 정방향으로 갔을때 5원에서 1가지 조합을 만들수 있다. 그리고 10원에 갔을때 10-5를 한 5원에서 dp가 1인데 이 1이 5원으로 만든것인지 다른 동전으로 만든것인지 애매해 진다. 또한 dp[0]은 1로 정한다. 0에 도달한 동전이라면 그 금액을 만드는 조합이 1개 있다는 뜻이기 때문이다.

## 어려웠던 점
반복문을 3중이나 쓰고 역순으로 진행한다는 아이디어가 어려웠다.

## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, k;
vector<pair<int,int>> coins;
vector<int> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> t >> k;

    coins = vector<pair<int,int>>(k);
    dp = vector<int>(t+1);
    dp[0] = 1;

    for(int i = 0; i < k; i++){
        int p, n;
        cin >> p >> n;
        coins[i].first = p;
        coins[i].second = n;
    }
    for (int i = 0; i < k; i++) {
        for (int j = t; j >= 0; j--) {
            for (int u = 1; u <= coins[i].second; u++) {
                if(j-coins[i].first*u < 0) break;
                dp[j] += dp[j-coins[i].first*u];
            }
        }
    }
    cout << dp[t];
    return 0;
}