[ 백준 9084 ] 동전 (C++)

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

[ 문제 바로가기 ]

[ 문제풀이 ]

금액 M원을 만들 수 있는 방법의 수를 구해야 하는 문제이다.

지금부터는 간단한 수식을 이용해서 문제에 대해 표현해볼 것이다.

F[A] = B 라는 수식을 사용할 것인데, 이 수식의 의미는 "A원을 만들 수 있는 방법은 총 B가지가 있습니다." 를 의미한다.

F[A] = B : A원을 만들 수 있는 방법의 수는 총 B가지가 존재합니다.

그럼 지금부터 간단한 예시를 통해서 문제에 접근해보자.

우리가 동전 [ 1 , 2 , 3 ] 원짜리 동전을 가지고 있고 이를 이용해서 '1원 ~ 3원'을 만드는 경우를 알아보자.

현재 우리의 상태는 [ 1 , 2 , 3 ] 원을 통해서 그 어떠한 금액도 만들어 보지 않은 상태이다.

그리고 지금부터는 특정 금액을 만드는 경우의 수를 구할 것인데, "가장 마지막에 해당 동전을 사용해서 금액을 완성시키는 과정" 을 통해서 알아 볼 것이다.

그 전에 ! 한가지만 간단하게 스치듯이 이야기하고 넘어갈 부분이 하나 있다.

과연, 주어진 동전을 이용해서 '0원'을 만들 수 있는 방법은 몇 가지가 있을까 ??

아주 간단하게 "모든 동전을 사용하지 않는 방법" 1가지가 존재한다.

따라서 우리는 F[0] = 1 이라고 정의할 수 있다.

물론 ! 문제에서 주어지는 금액 M은 1이상의 값이다. 하지만 풀이를 하기에 앞서, '0원을 만들 수 있는 방법은 1가지가 있다' 라고 알고 시작해보자.

F[0] = 1

#Case1 : 1원을 통해서 1원 ~ 3원 만들기

1. 1원을 "가장 마지막에 사용해서 1원을 완성시키기"

먼저, 1원짜리 동전을 가장 마지막에 사용해서 1원을 완성시켜보자.

그럼 ! 완성시키기 전에, "기존의 상태"에 대해서 부터 알아보자.

우리는 "기존의 상태 + 최종적으로 사용한 1원 = 1원" 이 되도록 만들어야 하는 상황이다.

그럼, 기존의 상태에서 우리는 몇 원을 가지고 있어야할까 ??

바로 0원이다. 0원을 가지고 있어야 "최종적으로 1원을 사용 함으로써 1원을 완성" 시킬 수 있기 떄문이다.

그럼 0원을 만들 수 있는 방법의 수는 몇 가지가 있을까 ?? 바로 한 가지이다.

그리고 우리는 이 한가지를 위에서 F[0] 라는 수식에 저장을 해놓았다.

즉 ! F[1] = 1 이 되는 것이다.

2. 1원을 "가장 마지막에 사용해서 2원을 완성시키기"

마찬가지로, "기존의 상태"에 대해서 부터 알아보자.

우리는 "기존의 상태 + 최종적으로 사용한 1원 = 2원" 이 되도록 만들어야 하는 상황이다.

그럼, 기존의 상태에서 우리는 몇 원을 가지고 있어야 할까 ??

바로 1원이다. 1원을 가지고 있어야 "최종적으로 1원을 사용 함으로써 2원을 완성" 시킬 수 있기 때문이다.

그럼 1원을 만들 수 있는 방법의 수는 몇 가지가 있을까 ?? 바로 한 가지이다.

그리고 우리는 이 한 가지를 F[1] 이라는 수식에 저장해 놓았다.

즉 ! F[2] = 1 이 되는 것이다.

3. 1원을 "가장 마지막에 사용해서 3원을 완성시키기"

기존의 상태는 "2원을 가지고 있어야 하는 상황" 이 된다.

그래야지, 기존의 상태 + 최종적으로 사용한 1원 = 3원 이 되기 떄문이다.

마찬가지로, 기존의 상태인 '2원을 만들 수 있는 방법의 수'는 우리가 위에서 구한 F[2]에 저장되어 있다.

따라서, F[2] = 1이기 때문에, F[3] = 1이 된다.

#Case2 : 2원을 통해서 1원 ~ 3원 만들기

1. 2원을 "가장 마지막에 사용해서 1원 만들기"

애초에 문제 자체가 잘못되어있다. 2원을 가장 마지막에 사용해서 1원을 만든다 ? 그럼 기존의 상태는 -1원을 가지고 있는 상태여야 하는데, -1원이라는 것은 존재할 수 없는 상태이다.

따라서, 불가능한 상황이다.

2. 2원을 "가장 마지막에 사용해서 2원 만들기"

이 상황은 "기존의 상태 + 최종적으로 사용한 2원 = 2원" 이 되도록 만들어야 하는 상황이다.

즉 ! 기존의 상태는 '0원'을 가지고 있어야 하는 상황인 것이다.

그럼 0원을 만들 수 있는 방법의 수는 ? F[0]에 '1'로 저장이 되어 있고, 따라서 F[2] = 1이 된다.

그런데 ! F[2] = 1이 맞을까 ?? 분명히 위에서 설명한 Case1에서 '1원짜리 동전을 최종적으로 사용함으로써 2원을 만드는 경우' 에서도 F[2] = 1 이라는 값이 설정되었다.

따라서, 값을 그대로 설정하는 것이 아닌, 더해가면서 경우의 수를 더해가면서 설정해 주어야 한다는 것이다.

즉 ! F[2] = 1 + 1  = 2 가 된다.

실제로 "2원을 만들 수 있는 방법"을 적어보면, "1 + 1" , "0 + 2" 로 2가지 방법이 있다.

"1 + 1" 은 Case1에서 진행한 "최종적으로 1원을 사용함으로써 2원을 만드는 경우" 에 속하는 식이고

"0 + 2" 는 지금 진행한 "최종적으로 2원을 사용함으로써 2원을 만드는 경우" 에 속하는 식이된다.

3. 2원을 "가장 마지막에 사용해서 3원 만들기"

기존의 상태는 1원을 가지고 있어야 하고, 이 기존의 상태에 2원짜리 동전을 하나 더해줌으로써 3원을 만들어 주는

상황이다. 그럼, F[1] = 1이라는 것을 Case1에서 구해놨으므로, F[3] = 1이 되는 것 같았지만, 위에서도 말했듯이, 경우의 수를 기존의 경우의 수에 더해가면서 저장해 주어야 하기 때문에 F[3] = 1 + 1 = 2 가 된다.

그럼 지금부터는 3원을 이용해서 금액을 맞추는 과정을 해보기 전에, 보다 일반화된 이야기를 한번 해보자.

우리는 "특정 동전을 최종적으로 사용함으로써, 최종적인 금액 X원을 완성시키기" 를 지금까지 계속했다.

그 과정에서, "기존의 상태, 즉, 기존에 얼마를 가지고 있어야 하는지"에 대해서 계속해서 파악했고, 결국 구해야 하는 것은 B원을 만들 수 있는 방법의 수 였기 때문에, "기존의 금액을 만들 수 있는 방법의 수"를 그대로 가져오는 방식으로 계산되었다.

그럼, 우리가 지금까지 계산한 1원과 2원을 이용해서 최종적인 금액 X원을 완성시킬 수 있는 방법의 수를 구하는 과정을 위에서 선언해 놓은 수식으로 표현해보면 다음과 같이 표현할 수 있다.

F[X] = F[X - 1] + F[X - 2]

위의 수식을 다시한번 정리해보면....

F[X - 1]이라는 것은 "X - 1원을 만들 수 있는 방법의 수"를 의미하고, 이 방법의 수가 의미하는 것은, "우리는 X - 1원을 만들어 놓고, 그 X - 1원에서 1원짜리 동전을 추가함으로써 X원을 만들 것입니다." 를 의미한다.

F[X - 2]이라는 것은 "X - 2원을 만들 수 있는 방법의 수"를 의미하고, 이 방법의 수가 의미하는 것은, "우리는 X - 2원을 만들어 놓고, 그 X - 2원에서 2원짜리 동전을 추가함으로써 X원을 만들 것입니다." 를 의미한다.

오해하지 말아야 할 부분이, 위의 식을 그대로 사용한다고 정답이 나오는 것이 아닌, 이 전에 나올 수 있는 모든 경우들에 대한 방법의 수가 저장되어 있어야 한다.

그럼 이런 일반화된 식으로 가지고, 3원짜리 동전을 이용해서 1 ~ 3원을 만드는 과정으로 넘어가보자.

Case3 : 3원을 통해서 1 ~ 3원 만들기

1. 3원을 "최종적으로 사용함으로써 1원 & 2원 만들기"

문제 자체가 잘못되어있다. 3원을 최종적으로 사용함으로써 최종적인 금액 1원 or 2원을 만들 수는 없다.

2. 3원을 "최종적으로 사용함으로써 3원 만들기"

기존의 상태에서는 0원을 가지고 있어야 하고, 이 상태에서 3원을 추가하면 됨으로 F[0]의 방법의 수를 그대로 가져오게 된다.

즉 ! F[3] = 2 + 1 = 3 이 된다. (기존에 2가지 방법이 이미 존재했으므로)

그럼 이제 [ 1 , 2 , 3 ] 원짜리 동전을 이용해서 3원을 만들 수 있는 경우의 수를 모두 적어봄으로써 확인해보자.

1. 1 + 1 + 1

2. 1 + 2

3. 0 + 3

위와 같이 3가지 방법이 있다.

위의 3가지 방법은 각각 "1원을 최종적으로 사용하는 경우", "2원을 최종적으로 사용하는 경우", "3원을 최종적으로 사용하는 경우" 를 나타내고 있다.

[ 소스코드 ]

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