[Algorithm] 동전 거스름돈 : 동적 계획 알고리즘

동전 거스름돈 문제는, 

그리디 알고리즘에 대한 개념을 소개하는 포스팅에서 간단하게 설명했었다.

 

대부분의 경우, 그리디 알고리즘으로 해결할 수 있으나 해결 못하는 경우도 있다.

동적 계획 알고리즘은 모든 동전 거스름돈 문제에 대하여 항상 최적해를 갖는다.

 

---

💡동적계획 알고리즘으로 접근

1️⃣ 부분 문제 찾기

이전 포스팅인 배낭 문제처럼, 동전 = 물건, 거스름돈 = 배낭의 무게 라고하면 배낭문제와 유사하게 정의된다.

동전을 1원씩 증가시켜 문제를 해결해 보자 -> 이 부분문제들의 해를 1차원 배열 C에 저장하자

• 1원을 거슬러 받을 때 사용되는 최소의 동전 수 C[1]
• 2원을 거슬러 받을 때 사용되는 최소의 동전 수 -> C[2]
• 3원을 거슬러 받을 때 사용되는 최소의 동전 수 -> C[3]
• ...
• n원을 거슬러 받을 때 사용되는 최소의 동전 수 -> C[n]

2️⃣ 중첩된 부문제 특성

배열의 해를 찾기 위해서는 부문제가 중첩되어 사용되기도 한다. -> 분할정복 알고리즘보다는 동적 계획법이 더 적합!

 

 

💡알고리즘 정리

• 동전 액면 w = {w1, w2, w3, ... , }  (w1 > w2 > w3 > ...)
• 각 액면의 동전이 거스름돈에 포함된 개수 x = { x1, x2, ... }
• 거스름돈 M
• 최적해 C(M)은 (k=1~n)까지의 xk를 모두 더한 값의 최솟값  :  (k=1~n)까지의 wk x xk = M

 

 

💡의사코드

• 입력 : 거스름돈 n원, k개의 동적의 액면, d1 > d2 > d3 > ... > dk = 1 (d = 동전 액면들)
• 출력 : C[n]

for i=1 to n: C[i]=무한대
C[0] = 0
for j=1 to n{ //j는 1원부터 증가하는 (임시)거스름돈 액수이고, j=n이면 입력에 주어진 거스름돈이 된다.
	for i=1 to k{ // 동전의 액면수까지
    	if(di <= j) and (C[j-di]+1<C[j])
        	C[j] = C[j-di]+1 //i가 1부터 k까지 고려해본 후, 가장 작은 값으로 갱신
    }
}
return C[n]

 

💡 C++ 코드

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <limits> // std::numeric_limits<int>::max();
using namespace std;

vector<int> W; // 동전의 액면가를 저장할 배열 
vector<int> C; // 

int main(){
    int n; // 거스름돈
    int k; // 동전의 액면 수

    int num[10000];
    char ch;
    int i=0;
    while(1){
        cin>>num[i];
        cin.get(ch);
        W.push_back(num[i]);
        if (ch == '\n')
         break;
        i++;
    }
    cin >> n;


    C.push_back(0);

    for(int i=1;i<=n;i++){
        C.push_back(1000);
    }

    for(int j=1;j<=n;j++){

        for(int i=0;i<W.size();i++){
            int W_cost = W[i];
            int pre_C = C[j-W_cost];
            if((W_cost <= j) && ((pre_C+1)<C[j]))
                C[j] = pre_C+1;
        }
    }

    cout << C[n];
}

 

 

⏰시간복잡도

• O(nk)
• 거스름돈 j가 1원~n원까지 변하며, 각각의 j에 대해서 최악의 경우 모든 동전 (d1, d2, d3, ..., dk)를 1번씩 고려하기 때문이다.