[백준 2624번] 동전 바꿔주기 (C++)

문제링크 : https://www.acmicpc.net/problem/2624

2624번: 동전 바꿔주기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, K;
int p[10001], n[1001];
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[i] >> n[i]; //금액, 갯수
    }

    dp[0]=1;

    for(int i=0; i<K; i++) //가짓수
    {
        for(int j=T; j>=0; j--) //총 금액
        {
            for(int k=1; k<=n[i]; k++) //현재 갯수
            {
                if(j-p[i]*k <0) continue; //범위조건
                dp[j] += dp[j-p[i]*k];
            }
        }
    }

    cout << dp[T];
    return 0;
}

 

동전의 총 가짓수, 금액, 현재 동전 갯수에 따라 3중 for문을 돌리는 dp문제이다.

먼저 초기값으로 dp[0]에 1을 넣어주고 시작한다.

dp에는 현재 금액에 따른 가짓수가 들어가게 된다.

 

현재 금액은 총 금액인 T부터 시작하며 점차 감소한다.

이 금액을 기준으로 현재 동전의 금액을 조정하여 dp값을 갱신하다.

주어진 동전마다 각 금액과 각 갯수를 따로 입력받았으므로, j-p[i]*k를 통해 최대 가능한 금액을 조정하며 값을 갱신한다.

해당 값의 경우 0 미만으로 내려갈 수도 있으므로 이 경우를 따로 예외처리 해준다.

 

처음 값 dp[20]에는 dp[20-5*1] = dp[15]로 0이 들어간다.

하지만 금액이 내려가다 보면 dp[5]에는 dp[5-5*1] = dp[0]으로 1이 들어가게 된다.

5원을 만드는 방법이 1가지 저장된 것이다.

 

금액이 1원일때도 보면,

dp[5-1*5] = dp[0]이므로 dp[5]에 1을 누적하여 더하게 된다.

이렇게 누적된 값들이 dp[20]을 만드는 과정에 더해지게 되어 총 경우의 수가 저장된다.

 

예시로 위에서 dp[15]의 경우 dp[15-5*3]으로 1이 저장되고,

dp[20] += dp[20-5*1]에 위에서 구한 dp[15]의 값이 사용되어 들어가는 것을 볼 수 있다.