[BOJ 2624] 동전 바꿔주기(C++, 다이나믹 프로그래밍)

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

2624번: 동전 바꿔주기

 

해설코드(C++).

 

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int T, k;
int dp[101][10001] = { 0 };
vector<pair<int, int>> v;
int val1, val2;
 
int main() {
    cin >> T;
    cin >> k;
    
    // k 인덱스 조정
    v.push_back(make_pair(0, 0));
    for(int i = 1;i <= k; i++){
        cin >> val1 >> val2;
        v.push_back(make_pair(val1, val2));
    }
    
    for(int i = 1; i <= k; i++){
        int mon = v[i].first;
        int cnt = v[i].second;
        for(int j = 0; j <= T; j++){
            // i - 1번째까지의 동전을 이용해 만든 값 복사
            dp[i][j] += dp[i - 1][j];
            
            // i번째 동전만으로 만들 수 있는 값 추가
            if(j == 0){
                for(int c = 1; c <= cnt; c++){
                    if(c * mon <= T)
                        dp[i][c * mon] += 1;
                }
            }
            // i - 1번째까지의 동전을 이용해서 만든 값에 i번째 동전을 추가
            else if(dp[i - 1][j] > 0){
                for(int c = 1; c <= cnt; c++){
                    if(j + c * mon <= T)
                        dp[i][j + c * mon] += (dp[i - 1][j]);
                }
            }    
        }
    }
    
    cout << dp[k][T] << endl;
    return 0;
}