[알고리즘]거스름돈나누어주기

소개

동전의 종류와 각 동전의 단위가 주어지며, 지불할 금액이 주어질 때 최소의 동전을 내어주는 프로그램을 작성하라.

입력파일의 첫째 줄에는 두 정수 n, c가 있는데 n은 사용되는 동전의 종류를 나타내고 c는 거스름돈을 나타낸다. 그리고 이어지는 n 줄에는 각 동전의 단위가 주어지며, 이 값은 큰 단위에서 적은 단위 순서로 되어 있다. 물론 마지막 동전의 단위는 1 이다. n은 10을 넘지 않으며, c는 1000을 넘지 않는다.

여러분은 거스름돈을 최소 개수의 동전으로 내어 줄 때 각 동전이 몇 개씩 내어 줘야 되는지를 결정하여 아래 보기에서와 같이 한 줄에 그 각각의 동전 개수를 출력하여야 한다. 만약 총 동전 개수는 동일하지만 내어 주는 방법이 다른 것이 존재할 경우 단위가 큰 것을 우선적으로 내어주는 방법으로 거스름돈을 지불한다. 아래에서 보인 예에서 동전의 개수를 최소로 하면서 28원을 내어 주는 방법은 7원->4개, !0원->2개 + 7원->1개 + 1원->1개, 2가지 방법이 존재하지만 단위가 큰 것을 우선 사용하는 방법은 출력 결과와 같다.

출력 시 각 값 사이엔 공백 문자를 삽입하여 구분한다.

컴파일 실행환경

비주얼 C++ 6.0

본문내용

#include <iostream.h>
#include <fstream.h>

int C[10][1000];
int n;
int denom[10];
int t_denom[10];
int used[10][1000];
int change;
int i;
int j;

int main(void)
{
ifstream fin("1.inp");
ofstream out("1.out");

if(!fin)
return -1;

fin>>n;
fin>>change;

for (i=1;i<=n;i++){
fin>>denom[i];
t_denom[i]=0;
//cout<<denom[i]<<" ";
}

참고자료

· 없음