[Dynamic Programming#2] 또 다른 동전 문제

이전 포스팅에서는 Change Making  문제를 다뤘다. 

이번 동적 프로그래밍 문제에서는 '주어진 동전의 종류를 이용하여 목표치(W)를 만드는 경우의 수 카운트' 문제를 풀어보도록 한다. 알고리즘을 단번에 생각해내기가 상당히 어렵다. 차근차근 이 문제를 접근해보자

예를 들어 설명하는 것이 가장 빠를 듯 하다.

1원 2원을 이용하여 4원(W)을 만드는 경우의 수는 몇 가지인가?

1+1+1+1 = 4

2+1+1    = 4

2+2       = 4

이렇게 총 3가지가 된다.

1원 2원을 이용하여 5원(W)을 만드는 경우의 수는 몇 가지인가?

1+1+1+1+1 = 5

2+1+1+1    = 5

2+2+1       = 5

이렇게 총 3가지가 된다.

자세히 보면, 1원으로 W를 만드는 경우의 수 + 2원을 이용하여 W를 만드는 경우의 수로 결과가 나타남을 알 수 있다. 즉, 위처럼 W=4 또는 W=5일 경우, 둘 다 1+2=3가지로 나타난다.

그럼 1원 2원 5원을 이용하여 5원(W)를 만드는 경우의 수는 몇 가지인가?

1+1+1+1+1 = 5

2+1+1+1    = 5

2+2+1       = 5

위의 1원 2원으로 5원을 만드는 경우의 수에 

5           = 5 가 하나 추가되어 총 4가지이다. 더 자세히는,

1원으로 W를 만드는 경우의 수 +

2원을 이용하여 W를 만드는 경우의 수 +

5원을 이용하여 W를 만드는 경우의 수 = 1+2+1 = 4 인 것이다.

또한 알 수 있는 것이 W가 어떤 값이든 1원으로 W를 만들 수 있는 경우의 수는 무조건 1가지이다... 당연 1+1+1+1... 이런식으로 W를 한 가지 경우로 만들 수 있으니 말이다.

그럼 2원으로 W를 만들 수 있는 경우는 

W-(2*1)원에서 1원으로 W-(2*1)원을 만드는 경우의 수 +

W-(2*2)원에서 1원으로 W-(2*2)원을 만드는 경우의 수 +

W-(2*3)원에서 1원으로 W-(2*3)원을 만드는 경우의 수 +

...

...

W-(2*k)원에서 1원으로 W-(2*k)원을 만드는 경우의 수 

이다. 여기서 당연히 k값은 2*k 값이 W값을 넘지 않도록 하는 값이다.

그럼 5원으로 W를 만들 수 있는 경우는 

W-(5*1)원에서 2원으로 W-(5*1)원을 만드는 경우의 수 +

W-(5*2)원에서 2원으로 W-(5*2)원을 만드는 경우의 수 +

W-(5*3)원에서 2원으로 W-(5*3)원을 만드는 경우의 수 +

...

...

W-(5*k)원에서 2원으로 W-(5*k)원을 만드는 경우의 수 

이다. 여기서 당연히 k값은 5*k 값이 W값을 넘지 않도록 하는 값이다.

여기서 2원으로 W-X원을 만드는 경우의 수는 앞서 2원으로 W를 만드는 경우의 수에서 이미 구한 값이다. 즉 앞서 저정된 값을 이용하는 동적 프로그래밍이라는 것을 여기서 알 수 있어야 한다. 

설명이 제대로 된지 모르겠다. 보통 동적 프로그래밍이 행렬 표로 설명하면 쉽듯이 행렬로 표현해보자.

즉, 1원 2원 5원으로 5원을 만드는 경우의 수는 위의 행렬에서 가장 오른쪽 하단에 있는 값이 되겠다.

위의 사진으로 이해가 됬으면 한다.

코드로 짜보면 다음과 같겠다.

 
using namespace std;
 
int main(){
 
    int TypeOfCoin, DesiredValue;
 
    cin >> TypeOfCoin >> DesiredValue;
 
    int* coins = new int[TypeOfCoin];
    int** destValue = new int*[TypeOfCoin];
    for (int i = 0; i < TypeOfCoin; i++){
        destValue[i] = new int[DesiredValue+1];
    }
        
 
    for (int i = 0; i < TypeOfCoin; i++)
        cin >> coins[i];
 
 
    for (int i = 0; i < TypeOfCoin; i++){
        for (int j = 0; j <= DesiredValue; j++){
            if (i == 0)
                destValue[i][j] = 1;
            else{
                destValue[i][j] = destValue[i - 1][j];
                for (int k = 1; j >= (coins[i] * k); k++)
                    destValue[i][j] += destValue[i - 1][j - (coins[i] * k)];
            }
        }
    }
 
 
    cout << destValue[TypeOfCoin - 1][DesiredValue] << endl;
 
 
 
 
    delete[] coins;
    for (int i = 0; i < TypeOfCoin; i++)
        delete[] destValue[i];
 
    return 0;
}
 

 

위의 코드는 동전의 종류 중 무조건 1원이 포함되는 경우일 것이다...