Dynamic Programming - Make Change Problem

N 개 타입의 동전으로 어떠한 금액을 만드는 것과 관련된 문제이다.

여기서 몇 가지 문제를 생각할 수 있는데,

1. Frobenius coin problem

이 문제는 NP-hard 문제로, GCD(최대공약수)가 1인 N 개 타입의 동전으로 만들 수 없는,

가장 큰 수를 찾는 문제이다. 이 수를 Frobenius(프로베니우스) number 라 한다.

하지만 N이 1,2,3 일 때는 다항시간에 찾을 수 있는 공식이 나와있다.

더 자세

한 내용은 위키피디아 http://en.wikipedia.org/wiki/Coin_problem 참고.

2. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가장 적은 수의 동전을 사용했을 때의 동전의 수.

(단 N >= 1 이고 N[1] = 1 )

요 문제는 Greedy 한 방법으로 풀어도 되지만, DP 방법으로 풀 수도 있다.

아이디어는

C-1 을 만드는 데 필요한 동전 갯수에 1원짜리 동전 하나를 더한 경우와

(C - 임의의 동전 가치) 를 만드는 데 필요한 동전 갯수 + 임의의 동전 1개인 경우를 비교해서

적은 쪽을 택하는 것.

점화식은 다음과 같다

M[C] = Change C 를 만들 때 사용하는 가장 적은 동전의 수 라고 했을 때,

M[C] = MIN( M[C-1]+1, M[C - V[j]]+1)        // 단, j = 1 ... N 이고 C >= V[j]

void minimum_coins() {
    int i, j;

    M[0] = 0;
    for(i = 1; i <= CHANGE; i++) {
        for(j = 0; j < NUM_OF_TYPES; j++) {
            if(i >= V[j])
                M[i] = MIN(M[i-1]+1, M[i-V[j]]+1);
        }
    }

}

3. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가능한 동전 조합의 경우의 수를 구하는 경우.

(단 N >= 1 이고 N[1] = 1 )

이 문제는 약간 어려웠던거 같다. 그냥 생각만으로는 잘 안되서,

아주 간단한 케이스를 가지고 종이에 적어가면서 확인했다.

아이디어는

D[i][j] = i 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수

i-1 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수에, i 번째 동전이 추가된 경우는 ==> ?

( j - i 번째 동전의 가치 * k) 의 경우의 수를 모두 더하는 것.

즉, 새로운 동전의 가치가 5 라면, { 5 }, { 55 }, { 555 } ... 가 추가되는 경우의 수를 모두 더하는 것.

점화식을 보자면, (여기서 동전의 타입의 넘버링은 0th ~ (N-1)th 까지로 생각한다)

( i == 0 인 경우 )

D[i][j] = 1    

( 아니라면 )

D[i][j] = D[i-1][j] + SUM(D[i-1][j-V[i]*k)        // k 는 자연수이고. j >= V[i]*k 인 경우.

void ways_to_make_change() {
    int i, j, k;

    for(i = 0; i < NUM_OF_TYPES; i++) {
        for(j = 0; j <= CHANGE; j++) {
            if(i == 0) {
                D[i][j] = 1;
            } else {
                D[i][j] = D[i-1][j];
                for(k = 1; j >= V[i]*k; k++) {
                    D[i][j] += D[i-1][j-V[i]*k];
                }
            }
        }
    }
}

조합의 수를 구하는 문제는 좀 헷갈리긴 했지만,

생각을 좀 해보고, 간단한 케이스를 확인해 보면서 찾을 수 있었다.