[Algorithm]Baekjoon 2642번 : 동전 바꿔주기

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

2624번: 동전 바꿔주기

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, k, p, n;
int dp[101][10001] = { 0 };
 
struct Node
{
    int money;
    int count;
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t >> k;
 
    vector<Node> nodes(k + 1);
    for (int i = 1; i <= k; ++i)
    {
        cin >> p >> n;
        nodes[i] = { p,n };
    }
 
    dp[0][0] = 1;
 
    for (int i = 1; i <= k; ++i) // 최대 100
    {
        int money = nodes[i].money;
        int count = nodes[i].count;
 
        for (int l = 0; l <= t; ++l)
        {
            for (int j = 0; j <= count; ++j)
            {
                if (l + money * j > t) break;
 
                dp[i][l + money * j] += dp[i - 1][l];
            }
 
        }
    }
 
    cout << dp[k][t];
}

 

밑에서부터 동전을 하나씩 더해가며 차곡차곡 값을 갱신하는 방식의 코드이다.

이건 말로 설명하기가 생각보다 어렵긴한데, 간단히 예시를 들면 아래와 같다.

 

3원짜리 동전 1개로는 3원을 표현할 수 있다. (주어진 여러 금액의 동전들 중, 3원짜리로'만' 표현할 때)

이 상태에서, 추가적으로 5원짜리 동전을 사용할 수 있다고 가정했을 때, 3원짜리 동전으로만 표현한 금액들에다가 5원짜리 동전을 슬쩍 얹어놓으면 , 5원짜리 동전'까지' 사용했을 때 만들 수 있는 금액과 dp테이블에 해당금액을 만들 수 있는 가짓수에 독립적인 값(중복되지 않는)을 누적시킬 수 있다. (이것이 57번째 라인을 의미한다)

 

dp[i][j] 는 i번째 종류의 동전만을 사용했을 때, j값을 만들 수 있는 경우의 개수이다.

동전인덱스를 1부터 시작한다고 가정하고(i를 1부터 시작), 1번째 인덱스의 동전값이 3이고 개수가 1개라고 가정하자.

그러면 dp[1][3]은 1이다. 1번째 동전, 즉 3원짜리 동전으로 3원을 표현하는 방법은 1가지라는 것이다. 

여기다가 2번째 동전인 5원짜리 한개를 슬쩍 얹어보자.

그러면 dp[2][8] += dp[1][3]이 된다. dp[2][8]은 두번째 동전까지를 사용했을 때, 8원을 만드는 경우의개수를 구하는것이니  dp[1][3]에다가 5원짜리 동전 하나를 사용하면 그게 8원이 되기때문에 누적시킬 수 있는 것이다.

 

 

 

 

이렇게 2차원dp로 하는방식 말고도, 1차원으로도 푸는 방법이 있다.

이건 어떻게 설명해야할지 헷갈리는데, 최대값부터 업데이트하기 때문에 0부터 업데이트하는 방식에서의 중복된값계산을 피할 수 있는 것 같다.

배낭문제에서도 적용되는 원리이다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, k, p, n;
int dp[10001] = { 0 };
 
struct Node
{
    int money;
    int count;
};
 
vector<Node> nodes;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t >> k;
 
    for (int i = 0; i < k; ++i)
    {
        cin >> p >> n;
        nodes.push_back({ p, n });
    }
 
    dp[0] = 1;
 
    for (int i = 0; i < nodes.size(); ++i) // 최대 100
    {
        int money = nodes[i].money;
        int count = nodes[i].count;
 
        for (int j = t; j >= 0; --j) // 최대 10000
        {
            for (int k = 1; k <= count && j - money * k >= 0; ++k)
            {
                dp[j] += dp[j - money * k];
           }
        }
        int asdf = 0;
    }
 
    cout << dp[t];
}