#include <stdio.h>
int coin[6]={0}; //가지고 있는 동전의 개수 [0]=500원 [1]=100원 [2]=50원 [3]=10원 [4]=5원 [5]=1원
int answer[6]={0}; //내야하는 동전의 개수
int won[6]={500, 100, 50, 10, 5, 1};
int price(int w); //동전 개수 맞추기
int main(void)
{
int w, i, result=0; //w=구입하려는 물건의 값
//입력
scanf(" %d", &w);
for(i=0; i<6; i++)
scanf(" %d", &coin[i]);
//계산
price(w);
for(i=0; i<6; i++)
result+=answer[i];
//정답 출력
printf("%d\n", result);
for(i=0; i<6; i++)
printf("%d ", answer[i]);
return 0;
}
int price(int w)
{
int sum=0, i, j, a, k, more, f;
if(coin[5]>=(w%10)) //won[i]원의 개수가 물건의 값의 일의 자리 수보다 클 때
{
sum=w%10;
answer[5]=w%10;
coin[5]-=w&10;
}
else //won[i]원의 개수가 물건의 값의 일의 자리 수보다 작을 때
{
sum=w%10;
answer[5]=(w%10)-5;
coin[5]-=(w%10)-5;
answer[4]++;
coin[4]--;
}
for(i=4; i>=0; i--)
{
f=coin[i];
for(j=1; j<=f; j++)
{
a=sum+won[i];
if(a<=w) //물건 값보다 적거나 같은 경우
{
sum+=won[i];
answer[i]++;
coin[i]--;
if(a==w)
return 0;
}
else //물건 값보다 초과한 경우
{
more=a-w; //초과한 금액
a-=more;
for(k=i+1; k<6; k++) //초과한 금액만큼 최소한의 동전 개수로 빼내기
{
if(won[k]<=more)
{
coin[k]+=more/won[k];
answer[k]-=more/won[k];
more-=(more/won[k])*won[k];
}
if(more==0)
break;
}
sum=a;
answer[i]++;
coin[i]--;
if(a==w)
return 0;
}
}
}
return 0;
}
2018.02.24 11:22
정올 - 알고리즘 - 동전자판기(下)(1183)
조회 수 902 추천 수 0 댓글 0