[이코테-그리디-예제] 거스름 돈 (Java)

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

풀이

거슬러 줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 수하라는 거스름 돈 N원을 넣으면, 거슬러 줄 동전의 최소 개수 X개를 반환하는 메서드를 작성해라로 해석할 수 있다.

거스름 돈 동전의 개수를 최소로 하려면, 금액이 가장 큰 동전부터 거슬러 주면 된다.
즉, 사용할 동전으로 나눠 떨어질 때까지의 몫의 합을 사용된 동전의 개수로 사용하면 된다.

코드

• 코드
• 테스트 케이스