[Dynamic Programming#1] change making problem

change making problem
[https://en.wikipedia.org/wiki/Change-making_problem]

위키피디아에서 알 수 있듯이 이 문제는,

'주어진 동전의 종류를 조합하여 목표 금액을 만들고자 할 때, 

최소의 동전 개수를 구하는 문제'

예를 들면, 다음 문제와 같다.

'1원 5원 10원을 가지고 15원을 만들고자 할 때,

15원을 만드는 조합 중 최소의 동전 개수는?'

Greedy한 방식으로도 풀 수 있지만 이 문제는 가장 기초적인 동적 프로그래밍(Dynamic Programming)로 해결할 수 있는 문제 중 하나이다.

아이디어는 다음과 같다.

1원이 포함된 n가지 동전으로 W원을 만들고자 할 때, 

W원을 만드는 최소의 동전 개수는 다음 두가지 경우의 수 중 최소값이다.

(1) W-1원을 만드는 최소 동전 개수 + 1원을 추가하여 W원을 만드는 경우

(2) W-(특정 동전의 값)원을 만드는 최소 동전 개수 + 특정 동전을 하나 추가하여 W원을 만드는 경우

예를 들면, 아까 위의 문제처럼 15원을 만들고자 할 때,

14원에서 1원을 추가해서 15원을 만드는 경우와

10원에서 5원을 추가해서 만드는 경우 중 

더 적은 동전의 수를 가지고 15원을 갖는 경우를 찾는 것이다.

따라서 이 문제는 W를 1원부터 목표 15원까지 차례로 구하면서 

이전의 저장된 값을 이용함으로 동적프로그래밍으로 해결할 수 있는 것이다.

대충 코드를 짜보면 다음과 같다.

int Min(int a, int b){
    return (a >= b) ? b : a;
}
 
int main(){
 
    int N, K;
 
    cin >> N >> K;
 
    int* coins = new int[N];   //코인 종류
    int* destValue = new int[K + 1];  //목표가 15원이라면 1~15원까지 최소동전 개수 담을 배열
 
    for (int i = 0; i < N; i++)
        cin >> coins[i];
 
    destValue[0] = 0;
    for (int i = 1; i <= K; i++){
        int min = K;
        for (int j = 0; j < N; j++){
            if (i >= coins[j]){
                destValue[i] = Min(destValue[i - 1] + 1, destValue[i - coins[j]] + 1);
                if (min>destValue[i])
                    min = destValue[i];        //i원 가치를 만들 때, 조합 중 최소값을 구함
            }
        }
        destValue[i] = min;
    }
 
    cout << destValue[K] << endl;    //목표 K값 최소 동전 개수 출력
        
 
    delete[] coins;
    delete[] destValue;
 
    return 0;
}