자동판매기 동전교환 timer 1s memory 64MB

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

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

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

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