1.5 금액 맞추기 : problem

* 코드 1-11에 중복 계산이 있을까?

화폐의 종류를 다르게 지정할 경우 없을 것이다.

* 지불하는 방법을 모두 출력하도록 프로그램을 수정하라

#include <iostream> 

#include<cstdio>

#include <string>

#define MAXN 50 // main()에서 사용

using namespace std;

int pay(int money, int bills[], int n, int num_bills, string s)

{

int count = 0;

int i, t;

if (n == 1)

{

if (money % bills[0] == 0)

{

string s2 = to_string(bills[0]) + " * " + to_string(money / bills[0]) + "\n";

s = s + s2;

std::cout << s <<std::endl;

return 1;

}

else

return 0;

}

t = money / bills[n - 1];

for (i = 0; i <= t; i++)

{

string s2 = to_string(bills[n - 1]) + " * " + to_string(i) + " + ";

string s3 = s + s2;

count += pay(money - bills[n - 1] * i, bills, n - 1, num_bills, s3);

}

return count;

}

int main()

{

int num_bills, money, i;

int bills[MAXN];

string s="";

printf("input number of bills : ");

scanf_s("%d", &num_bills);

printf("input bills : ");

for (i = 0; i < num_bills; i++)

scanf_s("%d", &bills[i]);

printf("input money : ");

scanf_s("%d", &money);

printf("answer : %d\n", pay(money, bills, num_bills, num_bills, s));

system("pause");

return 0;

}