1.5. 금액 맞추기 알고리즘

문제. 심각한 인플레이션을 겪고 있는 어느 나라에서는 1, 2, 5, 10, 20, 50만 원의 여섯 가지 지폐를 사용한다.

 

이러한 지폐 종류를 이용하여 100만원을 지불하는 방법은 모두 몇 가지 인가?

 

 

1.

 

#include <iostream>
 
using namespace std;
int main(void){
    int bills[6] = {1, 2, 5, 10, 20, 50};
    int count = 0, money = 100, i0, i1, i2, i3, i4;
    
    for(i0 = money; i0 >=0 ; i0-= bills[0])
        for(i1 = i0; i1 >= 0; i1 -= bills[1])
            for(i2= i1; i2 >= 0; i2 -= bills[2])
                for(i3 = i2; i3 >= 0; i3 -= bills[3])
                    for(i4 = i3; i4>= 0; i4 -= bills[4])
                        if(i4 % bills[5] == 0)
                            count++;
    
    cout<<count;
    return 0;
}

 

이런 식의 코드 작성은 문제를 해결하는데 부족함이 없지만, 지폐의 종류와 지불해야 하는 액수의 종류를 더 늘릴 때 문제가 발생한다.

 

 

2. 그러므로 직접 지폐의 종류와 액수를 입력받아서 해결하는 프로그램을 작성하는 방법을 생각해보자.

 

나는 재귀적 방법을 사용하기로 했다.