백준 2624번 - 동전 바꿔주기

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

2624번: 동전 바꿔주기

 

필요한 배경지식

• 다이나믹 프로그래밍

 

문제 해결 방법

동전의 순서는 중요하지 않으므로 동전별로 차례대로 K원을 몇개나 만들 수 있는지 다이나믹 프로그래밍 하면 된다.

문제에서 주어진 입력으로 예를 들어보겠다.

 

dp[K]를 'K원으로 만들 수 있는 동전조합의 수' 라고 할때

먼저 base case로 dp[0] = 1 을 정의할 수 있다. ('0원을 만들 수 있는 경우는 한가지'라고 인식해도 좋다.)

 

첫번째로 5원짜리 3개가 주어지면

dp[0] = 1 이므로 0원에서 5원, 10원, 15원을 각각 더한 값의 동전조합 수에 dp[0]을 더하면 된다.

즉, dp[5] =1, dp[10] = 1, dp[15] = 1 이 업데이트 될 수 있다.

 

그 다음 10원짜리 2개에서는

dp[0], dp[5], dp[10], dp[15] 가 각각 1이므로

0, 5, 10, 15원에 각각 10, 20을 더한 값의 동전조합 수에 dp[0], dp[5], dp[10], dp[15]를 더해주면 된다.

이때, T = 20 이므로 20을 넘어가는 값을 제외하면

10원에서 10원을 더한 동전조합 수 dp[20] = dp[20] + dp[10] = 1

5원에서 10원을 더한 동전조합 수 dp[15] = dp[15] + dp[5] = 2

0원에서 10원을 더한 동전조합 수 dp[10] = dp[10] + dp[0] = 2,

0원에서 20원을 더한 동전조합 수 dp[20] = dp[20] + dp[0] = 2

(큰수부터 작은수 순으로 계산한 이유는 직접 작은 수부터 큰수까지 계산하여 알아보자...!!)

 

마지막으로 1원짜리 5개도 같은 방식으로 계산해보면

15원에서 1*5원을 더한 동전조합 수는

dp[20] = dp[20] + dp[15] = 4 로 답을 구해낼 수 있다.

(나머지 자세한 계산은 생략했다.)

 

 

전체코드

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;

int T,K, p,n;
vector<pii> v;
int dp[10001]{};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>T>>K;
    for(int i=0; i<K; i++){
        cin>>p>>n;
        v.push_back({p,n});
    }

    dp[0] = 1;
    for(int i=0; i<K; i++){
        int cp = v[i].xx;
        int cn = v[i].yy;
        for(int t=T-cp; t>=0; t--){
            if(dp[t]==0) continue;
            for(int j=1; j<=cn; j++){
                int nt = t + cp*j;
                if(nt > T) break;
                dp[nt] += dp[t];
            }
        }
    }

    cout<<dp[T];
}