[백준 3067번] Coins (C++)

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

3067번: Coins

DP문제로 아주 유명한 문제이다.

DP가 큰 문제를 작은 문제로 나눠 생각해서 작은 문제를 통해 큰 문제를 해결하는 방식이므로 문제를 쪼개야한다.

예를 들어 1000원을 만드는 방법의 수를 구해야 한다면, 주어진 동전으로 1원을 만드는 경우의 수, 2원을 만드는 경우의 수, 3원을 만드는 경우의 수... 계속 나아가서 1000원까지 도달하는 방식으로 DP를 구성해 주면 된다.

 

DP배열의 크기는 구해야하는 돈의 크기이므로 int dp[1001] 이 된다. 주어진 돈의 종류는 1원과 2원이라고 해보자. 1원을 사용한 경우, 1원을 만들기 위한 경우의 수는 1이다. dp[1] = 1이다. 1원짜리 동전을 사용해서 1000원까지 표현하는 경우의 수는 모두 1원만 사용하는 1가지 경우 밖에 없으므로 dp[1]~dp[1000] = 1이 된다.

 

이제 2원을 사용하는 경우를 살펴보자. 2원을 사용해서 1원을 만드는 것은 말이 안되므로 2원을 만드는 경우부터 생각해주면 된다.2원을 사용해서 2원을 만들기 위해서는 이전의 값이 0원이어야 2원을 더해서 2원을 만들 수 있다. 그리고 아까 1원만을 사용해서도 2원을 만들지 않았던가. 따라서 0원에 2원을 더해서 2원이 되는 경우 + 기존에 있던 1원으로만 2원을 만든 경우가 dp[2]가 된다.수식으로 표현하면 dp[2] = dp[2] + dp[0] 이다. (이것 때문에 dp[0] = 1을 세팅하는 작업이 필요하다)

 

마지막으로 한번만 더 살펴보자 2원을 사용해서 3원을 만들기 위해서는 1원에 2원을 더해야 한다. 따라서 1원을 만들 수 있는 모든 경우에 2원을 더하는 경우(dp[1]) + 기존에 2원을 사용하지 않고 3원을 만든 경우(dp[3])가 dp[3]의 값으로 갱신된다. dp[3] = dp[3] + dp[1])

 

**이해를 돕기 위해 하나 더 써보자면, 6원짜리 동전이 추가로 있었고 10원을 만드는 경우를 구하고 싶다면

dp[10] = dp[10](기존 1원과 2원만을 이용해서 10원을 만든 경우) + dp[4](1원과 2원을 사용해서 4원을 만든 경우에 6원 짜리 동전을 사용해 10원을 만든 경우)가 되겠다.

 

따라서 점화식은 dp[n] = dp[n] + dp[n-동전의 값] 이다.위와 같이 계속하여 dp값을 갱신해서 dp[1000]까지 구하면 모든 경우의 수를 다 따져볼 수 있다.

 

 

코드는 다음과 같다.

#include <iostream>
#include <cstring>
#define endl "\n"
#define ll long long
using namespace std;

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int t,n,m;
    int coin[21];
    ll dp[10001] = {0,};
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1 ; i < n+1; i++){
            cin >> coin[i];
        }
        cin >> m;
        dp[0] = 1;
        for(int i = 1; i < n+1; i++){
            for(int j = coin[i]; j < m+1; j++){
                dp[j] = dp[j] + dp[j-coin[i]];
            }
        }
        cout << dp[m] << endl;
        memset(dp,0,sizeof(dp));
    }
}