백준 2293 - 동전 1 (C++)

 

 

동전이 여러 종류가 주어졌을 때, 각 동전을 사용해서 K원을 만드는 경우의 수를 구하면 된다.

 

주의할 점은 1 + 1 + 2 로 4원을 만드는 것과 2 + 1 + 1 로 4원을 만드는 것은 같은 경우로 친다.

(순서만 바뀌는 것은 같은 경우이다.)

 

문제 풀이

이 문제는 다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

코드는 간단하지만, 아이디어를 구상하는 것이 다소 어려울 수 있다.

 

먼저, 입력으로 주어진 동전은 (1, 2, 5) 3개이며, K는 10이라고 가정해보자.

 

먼저, 다이나믹 프로그래밍은 무엇을 기준으로 DP배열을 만드느냐가 첫 번째 관문이다.

해당 문제에선 우리가 찾고자 하는 것이 k원을 만드는 대한 경우의 수이다.

그러므로, DP배열의 i번 인덱스에는 i원을 만드는 경우의 수를 저장할 것이다.

 

Ex) DP[5] 는 주어진 동전을 사용해 5원을 만드는 경우의 수

 

그렇다면, 이제 점화식을 세워보자.

 

10원을 만드는 경우의 수를 생각해보자.

 

만약, 1원부터 9원까지 만들 수 있는 경우의 수가 모두 구해진 상태라고 가정을 해보자.

이 때, 우리에게 주어진 동전은 (1, 2, 5) 총 3가지가 있다.

 

그렇다면, 1원을 더해서 10원을 만드는 경우를 생각해보자.

1원을 더해서 10원이 되려면 9원에 1원을 더해야 한다.

 

즉, 1원을 더해서 10원을 만드는 경우의 수는 9원을 만드는 경우의 수라고 할 수 있지 않을까?

 

만약, 2 + 2 + 2 + 1 이라는 조합으로 9를 만들었다고 해보자.

 

여기의 끝에 1을 더해서, 2 + 2 + 2 + 1 + 1 을 하면 10이 된다.

즉, 9에 1을 더해서 10을 만드는 경우의 수는 결국 9를 만드는 경우의 수가 된다.

 

똑같이 2원을 더해서 10원을 만드는 경우의 수는 8원을 만드는 경우의 수가 되고, 5원을 더해서 10원을 만드는 경우의 수는 5원을 만드는 경우의 수가 된다.

 

주어진 입력에 대해 점화식을 세워보면, DP[10] = DP[9] + DP[8] + DP[5] 라고 할 수 있다.

DP[9]도 동일한 방식으로 DP[8] + DP[7] + DP[4]로 표현할 수 있으며 DP[8]과 DP[5]도 마찬가지의 논리가 적용된다.

 

즉 동전의 가치가 (A1, A2, A3 ....  An)이렇게 주어진다면, DP[K] = DP[K - A1] + DP[K - A2] ...... + DP[K - An] 이 된다.

이 점화식을 코드로 구현해보면 답을 구할 수 있다.

 

풀이 코드

int NumCoin = 0;
int TargetMoney = 0;
std::cin >> NumCoin >> TargetMoney;

std::vector<int> Coins(NumCoin);
std::vector<int> DP(TargetMoney + 1);

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

먼저, 입력을 모두 저장해주자.

 

DP[0] = 1;

for (int i = 0; i < NumCoin; i++)
{
    for (int j = Coins[i]; j <= TargetMoney; j++)
    {
        DP[j] += DP[j - Coins[i]];
    }
}

다음은 DP[0]을 1로 초기화해준 뒤, 반복문을 돌려주었다.

0원을 만드는 경우도 1가지 있으니, DP[0] = 1로 초기화 해주었다.

 

이제, 각 동전에 대해 마지막으로 동전을 더해서 j원을 만드는 경우를 계산해 주었다.

동전의 가치보다 작은 금액은 만들 수 없으므로 j는 Coins[i]부터 시작하도록 하였다.

 

Coins[i] 가 2원인 경우, 마지막으로 2원을 더해서 2원을 만드는 경우, 3원을 만드는 경우, 4원을 만드는 경우 ....... 10원을 만드는 경우까지 갱신해주는 것이다.

std::cout << DP[TargetMoney];

return 0;

모두 갱신한 뒤 답을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCoin = 0;
    int TargetMoney = 0;
    std::cin >> NumCoin >> TargetMoney;

    std::vector<int> Coins(NumCoin);
    std::vector<int> DP(TargetMoney + 1);

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

    DP[0] = 1;

    for (int i = 0; i < NumCoin; i++)
    {
        for (int j = Coins[i]; j <= TargetMoney; j++)
        {
            DP[j] += DP[j - Coins[i]];
        }
    }

    std::cout << DP[TargetMoney];

    return 0;
}