[ 프로그래머스 거스름돈 (Lv3) ] (C++)

프로그래머스의 거스름돈(Lv3) 문제이다.

[ 문제풀이 ]

주어지는 거슬러줘야 하는 돈을, 가지고 있는 금액을 통해서 거슬러 줄 수 있는 경우의 수를 모두 구해야 하는 문제이다.

이는, 다르게 말하면 주어진 금액들을 통해서 주어진 금액을 만들 수 있는 경우의 수를 구하는 것과 동일하다.

그럼 지금부터 하나의 수식을 이용해서 이를 표현해보자.

F[A] = B 라는 수식을 사용할 것인데, 이 수식의 의미는 "주어진 금액들로 A원을 만들 수 있는 방법은 총 B가지가 있습니다." 를 의미한다. 그리고 이 수식의 기본 베이스가 되는 값을 딱 하나만 설정해 놓고 시작을 하자.

F[0]의 값이다. F[0]을 의미에 입각해서 풀어보면, "주어진 금액들로 0원을 만들 수 있는 방법의 수" 이다.

즉, 주어진 금액을 하나도 사용하지 않으면 되기 때문에, F[0] = 1이 된다.

그럼 하나의 예시를 가지고 문제에 접근해보자.

'4원'을 [ 1 , 2 ] 원을 통해서 만들 수 있는 경우의 수를 구해보자.

그럼 우리는 지금부터 '4원'을 만들 수 있는 경우의 수를 구하기 위해서 위의 금액들로 1원 ~ 4원을 만들 수 있는 경우의 수들부터 한번 구해보자. 조금 더 나아가서, "해당 동전을 가장 마지막에 추가함으로써 원하는 액수 만들기"를 한번 진행해보자.

#1. 1원으로 1 ~ 4원의 금액 만들기

1. "1원을 가장 마지막에 추가함으로써 1원 만들기"

   1원을 가장 마지막에 추가함으로써 1원이 되기 위해서는 기존에 가지고 있던 금액이 '0원'이여야 한다.

   우리는 계속해서 "해당 금액을 가장 마지막에 추가함으로써 ~" 라는 문구를 사용할 것이고, 이 상황을 만들기 위해서는

   위와 같이 "기존에 가지고 있던 금액"에 대한 계산이 필요하다.

   지금부터는 간편하게 "기존에 가지고 있던 금액"을 "기존금액" 이라고 표현하겠다.

   그래야 가장 마지막에 1원을 추가함으로써 전체 액수가 1원이 되게 만들 수 있다.

   즉, 0원을 만들 수 있는 경우의 수 만큼을 경우의 수로 가지게 될 것이다.

   F[0] = 1 이므로, F[1] = 1 이 될 것이다.

2. "1원을 가장 마지막에 추가함으로써 2원 만들기"

   1원을 가장 마지막에 추가함으로써 2원을 만들기 위해서는 기존금액이 1원이여야 한다.

   그래야, 마지막에 1원을 추가적으로 할당함으로써 전체 2원을 만들 수 있기 때문이다.

   즉, 1원을 만들 수 있는 경우의 수 만큼을 경우의 수로 가지게 될 것이다.

   F[1] = 1 이므로, F[2] = 1 이 될 것이다.

3. "1원을 가장 마지막에 추가함으로써 3원 만들기"

   기존금액은 2원이 될 것이고, F[2] = 1이므로, F[3] = 1이 될 것이다.

4. "1원을 가장 마지막에 추가함으로써 4원 만들기"

   기존 금액은 3원이 될 것이고, F[3] = 1이므로, F[4] = 1이 될 것이다.

우리는 이렇게 '1원'을 가지고 만들 수 있는 경우의 수들을 모두 구해 보았다.

F[0] = 1  / F[1] = 1 / F[2] = 1 / F[3] = 1 / F[4] = 1 이 된다.

#2. 2원으로 1 ~ 4원의 금액 만들기

1. "2원을 가장 마지막에 추가함으로써 1원 만들기"

   불가능한 경우이다. 내가 현재 추가하고자 하는 금액이 '2원'인데, 이 2원을 추가함으로써 전체 금액이 1원이 되야 한다는

   상황은 불가능한 상황이다.

2. "2원을 가장 마지막에 추가함으로써 2원 만들기"

   이 경우에 기존금액은 0원이 되어야 한다. 그래야 최종적으로 2원을 추가함으로써 최종금액 2원을 만들 수 있기 때문이다.

   즉, F[2] = F[0]가 된다. 그럼 F[2] = 1이 되는 것일까 ??

   아니다. 왜냐하면 우리가 #1에서 진행했던 과정에서 F[2] = 1이라는 값을 구했었다.

   즉, #1에서 구했던 결과로 보면, "2원을 만들 수 있는 경우의 수는 1가지가 있습니다." 라고 구해놓았는데,

   이 경우에 또 한가지 방법이 추가되는 것이다.

   즉, 기존의 F[2]에다가 현재 경우의 수를 더해주어야 하므로 F[2] = 2가 된다.

3. "2원을 가장 마지막에 추가함으로써 3원 만들기"

   이 경우에 기존금액은 1원이어야 한다. 즉, F[3] = F[3] + F[1]이 된다.

   따라서, F[3] = 1 + 1 = 2 가 된다.

4. "2원을 가장 마지막에 추가함으로써 4원 만들기"

   이 경우에는 기존금액이 2원이 되어야 한다.

   즉, F[4] = F[4] + F[2]가 되고, 이를 계산해보면 1 + 2 = 3으로 총 3가지 방법이 있다.

이렇게 하나하나 다 계산을 해보니 결과적으로 [ 1 , 2 ] 원을 통해서 '4원'을 만들 수 있는 방법의 수는 총 3가지(F[4])가 있다는 것을 구할 수 있었다. 그럼, 이제 일반화된 식으로 이를 표현해보자.

"A원을 추가함으로써, K원을 만들려고 하는 상황" 이라면, "기존상황의 금액인 K - A원을 만들 수 있는 방법의 수를 그대로 가져오게 되는 것" 이다.

즉, F[K] = F[K - A]가 되는데, 여기서 "기존의 K원을 만들 수 있는 또 다른 방법의 수가 계산되어 있을 수 있으므로" ,

F[K] = F[K] + F[K - A]가 된다.

이를 점화식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MODULER 1000000007
#define MAX 100010
using namespace std;
 
int DP[MAX];
 
int solution(int n, vector<int> money) 
{
    DP[0] = 1;
    for (int i = 0; i < money.size(); i++)
    {
        for (int j = money[i]; j <= n; j++)
        {
            DP[j] += DP[j - money[i]];
            DP[j] %= MODULER;
        }
    }
    int answer = DP[n] % MODULER;
    return answer;
}