백준 2294 - 동전 2 (C++)

 

 

n개의 동전이 주어졌을 때, n개의 동전으로 k원을 만들 수 있는 경우의 수 중 사용한 동전의 수가 최소인 경우를 구하면 된다.

 

예를 들어, 1원과 5원 동전이 주어진 경우 10원을 만들기 위해 1원을 10개 사용할 수도 있지만 5원을 2개만 사용하여 10원을 만들 수도 있다. 이 때는 2를 출력하면 된다.

 

문제 풀이

해당 문제는 다이나믹 프로그래밍 문제이다.

다이나믹 프로그래밍을 구현하기 위해선, DP배열과 점화식이 필요하다.

 

먼저, DP배열을 만들어보자. 해당 문제는 k원을 만드는데 필요한 동전의 최소 개수를 구하는 문제이다.

즉, DP배열의 k번째 인덱스는 k원을 만들기 위해 필요한 동전의 최소 개수를 저장하는 배열로 하면 좋을 듯 하다.

 

이젠, 점화식을 구성해보자.

 

DP[k] 의 k원을 만들기 위해 필요한 동전의 최소 개수이다.

먼저, (1, 2, 5) 이렇게 3가지 동전이 주어졌다고 해보자.

 

1개의 1원을 추가로 사용해서 k원을 만들고자 한다면 (k - 1)원에 1원을 더해야 할 것이다.

이 때, (k - 1)원을 만드는 경우에 1원을 더해서 k원을 만드는 경우를 구할 수 있다.

 

예를 들어, k가 10이라고 해보자.

그렇다면, 1원을 하나 더해서 10원을 만드는 경우의 수는 9원을 만드는 경우의 수와 같다고 할  수 있다.

9원을 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 로 만들었다면, 그 뒤에 + 1 만 추가해주면 되기 때문이다.

만약, 2 + 2 + 2 + 2 + 1 의 조합으로 9를 만들었다면, 똑같이 뒤에 + 1을 추가해 2 + 2 + 2 + 2 + 1 + 1 의 조합으로 10을 만들 수 있다.

 

그런데, 우리가 구하고자 하는 것은 10원을 만들기 위해 최소로 필요한 동전의 개수이다.

그렇다면, 9원을 만들기 위해 필요한 최소 동전의 개수 + 1을 하면 10원을 만드는데 필요한 최소 동전의 개수를 구할 수 있지 않을까?

 

즉, i원을 하나 더 사용해서 k원을 만드는 경우중 동전의 개수가 최소인 경우는 (k - 1)원을 만드는데 필요한 최소 동전의 개수 + 1인 것이다.

 

하지만, 우리는 동전의 개수가 1가지가 아니다.

2원도 있고 5원도 있다.

 

그러므로, (k - 2)원을 만드는데 필요한 최소 동전의 개수 + 1도 고려해야 하고 (k - 5)원을 만드는데 필요한 최소 동전의 개수도 고려해야 한다.

 

이를 점화식으로 세워보자.

 

주어진 동전이 (A1, A2, A3....An) 이라고 한다면

DP[K] = std::min(DP[K - A1], DP[K - A2], DP[K - A3] ..... , DP[K -An])이 되는 것이다.

이를 코드로 구현하면 답을 구할 수 있게 된다.

 

풀이 코드

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

std::set<int> Coins;
for (int i = 0; i < NumCoin; i++)
{
    int CurCoin = 0;
    std::cin >> CurCoin;

    Coins.insert(CurCoin);
}

입력을 받아주었다.

그런데 보면 동전을 vector에 저장하는 것이 아니라 set에 저장하고 있다.

그 이유는 문제의 조건중에 같은 가치의 동전이 주어질 수도 있다는 이유 때문이다.

 

이 문제는 2원짜리 동전이 하나만 주어져도 그 동전을 여러 번 사용할 수 있는 문제이다.

그런데 자료구조에 2원짜리 동전을 여러개 가지고 있다고 해서 결과가 달라질까?

 

2원짜리 동전이 자료구조에 1개만 있어도 100번 사용할 수 있기 때문에, 동전이 여러개 있는 것은 연산 낭비라고 생각했다. 그래서 set에 저장하여 중복을 제거하였다.

 

std::vector<int> DP(TargetMoney + 1, INT_MAX / 2);
DP[0] = 0;

std::set<int>::iterator CurIter = Coins.begin();
std::set<int>::iterator EndIter = Coins.end();

while (CurIter != EndIter)
{
    int CurCoin = *CurIter;

    for (int j = CurCoin; j <= TargetMoney; j++)
    {
        DP[j] = std::min(DP[j], DP[j - CurCoin] + 1);
    }

    CurIter++;
}

그리고, DP배열을 만들어서 위의 점화식을 코드로 구현해주었다.

모든 동전에 대해 j원을 만드는데 필요한 최소 동전 갯수를 구한 뒤, DP배열을 최소값으로 갱신해주었다.

 

이 때, DP배열은 INT_MAX가 아닌 INT_MAX / 2 로 초기화해주었는데, 그 이유는 DP[j - CurCoin] + 1 부분에서 오버플로우가 발생할 수 있기 때문이다.

 

if (DP[TargetMoney] == INT_MAX / 2)
{
    std::cout << -1;
}
else
{
    std::cout << DP[TargetMoney];
}

return 0;

마지막으로 답을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>
#include <set>
#include <climits>

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::set<int> Coins;
    for (int i = 0; i < NumCoin; i++)
    {
        int CurCoin = 0;
        std::cin >> CurCoin;

        Coins.insert(CurCoin);
    }

    std::vector<int> DP(TargetMoney + 1, INT_MAX / 2);
    DP[0] = 0;

    std::set<int>::iterator CurIter = Coins.begin();
    std::set<int>::iterator EndIter = Coins.end();

    while (CurIter != EndIter)
    {
        int CurCoin = *CurIter;

        for (int j = CurCoin; j <= TargetMoney; j++)
        {
            DP[j] = std::min(DP[j], DP[j - CurCoin] + 1);
        }

        CurIter++;
    }

    if (DP[TargetMoney] == INT_MAX / 2)
    {
        std::cout << -1;
    }
    else
    {
    	std::cout << DP[TargetMoney];
    }

    return 0;
}