백준 2239 - 동전 1

 

 

문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 동전으로 K를 만드는 경우의 수를 구하는 것이다.

이때, N개의 동전은 각각 다른 가치를 갖고 있다.

 

해당 문제는 DP를 통해 간단하게 풀 수 있다.

우선, {1, 2, 5}의 동전으로 10을 만드는 경우를 생각해 보자.

0을 만드는 방법은 동전을 모두 사용하지 않는 단 하나의 경우밖에 없다.

1을 만드는 방법 역시 1을 사용한 경우밖에 없다.

2를 만드는 방법은 [1, 1], [2] 로 두 가지 경우가 존재한다.

이는 1을 만드는 경우에 1을 추가한 경우와 2를 사용한 경우가 된다.

3을 만드는 방법은 [1, 1, 1], [2, 1]로 두 가지이다.

이는 2를 만드는 경우에 1을 추가한 경우와 1을 만드는 경우에 2를 추가한 경우를 통해 만들 수 있다.

하지만, 해당 경우에 [1, 2]와 [2, 1]은 같은 경우로 취급되기 때문에 한 번만 세야 한다.

 

처음에는 특정 수 i를 만들 때 각 동전을 사용할 경우를 생각해 [i - coin]개의 경우를 i를 만들 수 있는 경우에 추가하였다.

for(int i = 1; i <= K; i++)
{
    for (auto coin : Coins)
    {
        dp[i] += dp[i - coin];
    }
}

하지만, 이렇게 되면 앞에서 말했던 같은 경우로 취급하는 경우의 수를 모두 세어버리게 된다.

 

따라서, 반대로 적용해야 한다.

특정 동전 coin을 사용하여 만들 수 있는 i를 계산해 주는 것이다.

for (auto coin : Coins)
{
    for (int i = coin; i <= K; i++)
    {
        dp[i] += dp[i - coin];
    }
}

이렇게 하면 각 동전이 사용되는 경우를 한 번씩만 계산할 수 있게 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, K;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    vector<int> Coins(N, 0);
    vector<int> dp(K+1, 0);

    for (int i = 0; i < N; i++)
    {
        cin >> Coins[i];
    }

    dp[0] = 1;

    for (auto coin : Coins)
    {
        for (int i = coin; i <= K; i++)
        {
            dp[i] += dp[i - coin];
        }
    }

    cout << dp[K];

    return 0;
}

---