동전교환

동전교환

동전을 입력 받아 가장 적은 수의 동전으로 교환 해 주려면 어떻게 주면 되는가?

 

입력예시

15 //거스름돈

4 //동전 갯수

1 //동전

5

12

50

출력예시

3

5 5 5

소스

#include<stdio.h>
int cost,n,coin[10];
int change[20],chase[20];
void input()
{
 FILE *fp=fopen("input.txt","r");
 int i;

 fscanf(fp,"%d", &cost);
 fscanf(fp,"%d", &n);
 for(i=1;i<=n;i++)
  fscanf(fp,"%d", &coin[i]);
 fclose(fp);
}
void process()
{
 int i,j,min,k,f=cost;

 for(i=1;i<=cost;i++)
 {
  min=10000;
  for(j=1;j<=n;j++)
  {
   if(i-coin[j] >= 0 && min > change[i-coin[j]]+1)
   {
    min=change[i-coin[j]]+1;
    chase[i]=coin[j];
   }
  }
  change[i]=min;
 }
 printf("%d\n", change[cost]);
 while(1)
 {
  if(f==0) break;
  k=chase[cost];
  printf("%d ", k);
  f-=k;
 }
 printf("\n");
}
void main()
{
 input();
 process();
}