[ 백준 2293 ] 동전1 (C++)

백준의 동전1(2293) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예시를 통해서 어떤 원리로 답을 구할 수 있는지 알아보자.

나에게 { 1 , 2 , 3 } 원 짜리 동전이 있고 이를 이용해서 1원, 2원, 3원을 만드는 경우를 알아보자.

먼저, 당연한 이야기 하나만 알고가자. 위의 동전들을 사용해서 0원을 만들 수 있는 경우는 몇 가지가 있을까 ??

아무런 동전도 사용하지 않는 1가지 방법이 있다. 이 이야기는 왜 말했는지 아래쪽에서 알아보도록 하자.

가장 먼저 '1'원짜리만 사용해서 만들 수 있는 경우를 알아보자.

1원짜리를 1개 사용해서 1원 만들기

1원짜리를 2개 사용해서 2원 만들기

1원짜리를 3개 사용해서 3원 만들기

너무나도 당연한 이야기이다. 그럼 지금까지 '1'원을 만드는 경우의 수 = 1가지 / '2'원을 만드는 경우의 수 = 1가지 / '3'원을 만드는 경우의 수 = 1가지 가 되었다는 것을 확인할 수 있다.

그럼 '2'원짜리만 사용해서 만들 수 있는 경우를 알아보자.

2원짜리를 사용하게 되면, 절대로 '1'원을 만들 수는 없다. 왜냐하면 그 가치가 이미 2원이기 때문에 어떻게 조합을 하더라도 1원을 만들 수는 없다. 

2원짜리를 1개 사용해서 2원 만들기

2원짜리 1개 , 1원짜리를 1개 사용해서 3원 만들기

이렇게 2원짜리로 만들 수 있는 경우는 2가지가 존재한다.

즉 ! 지금까지 결과를 정리해보면...

'1'원을 만드는 경우의 수 = 1가지

'2'원을 만드는 경우의 수 = 2가지(1원짜리로만 2원만드는 방법 한가지 + 2원짜리로 2원만드는 방법 한가지)

'3'원을 만드는 경우의 수 = 2가지(1원짜리로만 3원 만드는 방법 한가지 + (1원짜리 + 2원짜리)로 3원 만드는 방법 한가지)

이제 3원짜리를 사용해보자.

3원짜리 또한, 그 가치가 이미 3원이기 때문에 어떻게 조합을 하더라도, 1원과 2원을 만들 수는 없다.

3원 짜리를 1개 사용해서 3원 만들기. 이렇게 한 가지 경우가 존재한다.

그럼 지금까지 결과를 정리해보면...

'1'원을 만드는 경우의 수 = 1가지

'2'원을 만드는 경우의 수 = 2가지(1원짜리로만 2원만드는 방법 한가지 + 2원짜리로 2원만드는 방법 한가지)

'3'원을 만드는 경우의 수 = 3가지(1원짜리로만 3원 만드는 방법 한가지 + (1원짜리 + 2원짜리)로 3원 만드는 방법 한가지 + 3원짜리로 3원 만드는 방법 한가지)

따라서, 주어진 K의 값이 '3'이였고, 사용할 수 있는 동전이 { 1, 2, 3 } 이었다면, 정답은 '3'이 된다.

그럼 지금부터는 위에서 구한 '3원' 을 조금 더 구체적을 알아보자.

먼저 '3원짜리 하나를 이용해서 3원을 만드는 방법' 을 알아보자.

이 상황은 풀어서 이야기하면, 0원에서 3원짜리 하나를 사용해서 3원을 만드는 상황이다.

두 번째로, '2원짜리를 사용해서 3원을 만드는 방법'을 보자.

이 상황은 '1원'에서 2원짜리 하나를 사용해서 '3'원을 만드는 상황이다.

세 번째로, '1'원짜리를 사용해서 1원을 만드는 방법'을 보자.

이 상황은, '2'원에서 1원짜리를 사용해서 '3'원을 만드는 상황이라고 볼 수 있다. 그런데 이 경우에는 애초에 '2원'이 있다고 가정을 했는데, 이 '2'원을 또한 만들 수 있는 방법이 여러가지가 존재한다.

지금부터 DP[] 라는 배열을 이용해서 이야기해보겠다. DP[a] = b 의 의미는 "a원을 만들 수 있는 경우의 수는 b가지 입니다." 라는 것을 의미한다. 즉 우리는 DP[K]의 값을 구해야 하는 상황이다.

첫 번째로 이야기했던, 0원에서 3원짜리를 하나를 사용해서 3원을 만드는 상황을 확인해보자.

즉, 이런 경우에는 DP[3] += DP[0]이 된다. 왜 ?? 0원을 만들 수 있는 경우의 수에서 3원 하나를 사용하는 경우이기 때문이다.

'2'원을 사용하게 되는 경우는 ?? DP[3] += DP[1] 이 된다. 왜 ?? 이 상황은 2원을 사용해서 3원을 맞추려고 한다. 그럼 ? 기존에 이미 1원을 가지고 있어야 하기 때문이다.

마지막으로 1원을 이용해서 만드는 방법을 보자.

이 경우에는 DP[3] += DP[2]가 된다. 왜 ? 현재 '1'원을 이용해서 3원을 맞추려면, 기존에 2원이 있어야 하고, 이 2원을 만드는 방법은 DP[2]에 저장되어 있기 때문이다.

즉 ! 현재 X원인 동전을 가지고 있다면, 이 동전을 이용해서 Y원을 만들고 싶다면, DP[Y] = DP[Y] + DP[Y - X]가 된다.

그 동전이 가진 가치만큼을 뺀 나머지 액수를 만드는 경우의 수가 더해진다는 것이다.

여기서 ! 아까 하지 못했던 이야기를 해보자. 가장 처음에 0원을 만들 수 있는 경우를 이야기 했었다. 1가지였다고 !

이게 이 문제의 초기식으로 적용되기 때문이다.

위에서 이야기했던 3원 짜리를 이용해서 3원을 만드는 경우를 보자. DP[3] = DP[3] + DP[3 - 3]이 될 것이고, 즉, DP[3] += DP[0]이 된다는 것이다. 이 때, DP[0]이 만약 0이라면 ?? DP[3] = 0이 될 것이다. 3원짜리를 이용해서 만들 수 있는 경우가 한 가지 존재하는데도 불구하고, 계산이 제대로 되지 않는다는 것이다.

또한, 위에서 글을 읽을 때 분홍색으로 표시된 글들을 다시 한번보자. "그 가치가 이미 ~원 이기 때문에, ~~원은 절대로 만들 수 없다" 와 같은 이야기를 했는데, 이 부분은 코드로 확인해보자.

DP[0] = 1;
for (int i = 1; i <= N; i++)
{
    for (int j = Coin[i]; j <= K; j++)
    {
        DP[j] = DP[j] + DP[j - Coin[i]];
    }
}

이게 코드이다. Coin배열에는 문제에서 주어진 동전의 가치들이 저장되어 있다.

그리고 line4)를 보게되면, j = Coin[i] 부터 K까지 반복하는 것을 볼 수 있다. 이게 바로 분홍색 글씨의 이유이다.

내가 현재 'x원'짜리를 이용해서 어떤 금액을 만들려면, 최소한 그 금액은 x원보다 크거나 같아야 한다는 것이다.

내가 만약 3원짜리 동전을 가지고 어떤 금액을 만들려고 하는데, 이 동전으로 1원 혹은 2원을 만드는게 가능하지는 않기 때문이다.

그리고 위의 코드를 전체적으로 이야기해보면, 각 동전이 돌면서 K원까지 만들 수 있는 경우의 수를 계속해서 더해주는 것이다.

바로, DP[ j - coin[i] ] 라는 식을 통해서 ! 이 식이 의미하는 것은 "내가 X원으로 Y원을 만들기 위해서는, Y - X원을 만드는 경우의 수 만큼을 더해줘야 한다." 라는 것이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N, K;
int Coin[MAX];
int DP[10010];
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> Coin[i];
}
 
void Solution()
{
    DP[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = Coin[i]; j <= K; j++)
        {
            DP[j] = DP[j] + DP[j - Coin[i]];
        }
    }
    cout << DP[K] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}