Azza's Blog

아이디어는

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);
        }
    }

}

아이디어는

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];
                }
            }
        }
    }
}