자동판매기 동전교환 > 문제은행



문제은행

1421 : 자동판매기 동전교환

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 12 회    시도횟수: 29 회   



작은 섬나라에는 동전이 50원, 10원, 5원, 1원짜리가 있다. 이 나라에서 사용하는 자동판매기는 지폐를 넣고 물건을 선택하면 잔돈을 동전으로만 거슬러주는데 손님의 편의를 위해 거슬러 주는 동전의 개수가 최소가 되도록 잔돈을 거슬러 준다.

 

e3050b66a1b29a01767400d7560a4131_1449744
 

즉 손님이 1000원 지폐를 자동판매기에 넣고 813원짜리 물건을 샀다면 거슬러 주어야 할 잔돈은 187원이 된다. 이때 거슬러 줘야할 동전을 50원짜리 3개, 10원짜리 3개, 5원짜리 1개, 1원짜리 2개가 된다.

그런데 어느 날 국가 정책으로 40원짜리 동전을 새로 만들어 사용하기로 결정했다. 그래서 자동판매기가 기존의 거슬러 주는 방법으로 동전을 거슬러 주면 항상 최소 개수의 동전을 거슬러 줄 수 없는 문제가 발생하게 되었다.

 

e3050b66a1b29a01767400d7560a4131_1449744
 

이제 이러한 문제를 해결하기 위해 항상 적은 개수의 동전을 거슬러 줄 수 있는 프로그램을 작성하시오.




한 줄에 자동판매기에 넣은 지폐의 금액 W(0≤W≤100,000)과 물건의 가격이 주어진다.



각 줄에 각 동전별(50 40 10 5 1) 순서대로 사용한 동전의 개수를 출력한다.


1000 863
1
2
0
1
2


100000 753
1984
1
0
1
2






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.