8.1 거스름 돈 알고리즘

물건을 팔고 가장 적은 개수로 거스름 돈을 주려면 어떻게 해야 할까요? 큰 단위의 돈을 주는 것이 작은 단위로 주는 것보다 유리하겠죠. 탐욕 알고리즘으로 문제를 해결한다면 큰 단위부터 거스름돈을 주게 전개합니다. 큰 단위 화폐부터 작은 단위 화폐 순으로 다음의 알고르즘을 전개합니다. 만약 단위보다 거슬러 줘야 할 돈이 많으면 몇 개를 줄 것인지를 결정합니다. 그리고 남은 돈은 다음 단위 화폐로 넘어가서 계산합니다. 이러한 방법을 계속 수행하면 가장 적은 개수로 거스름 돈을 지불할 수 있습니다.

먼저 화폐 단위를 열거형으로 정의합시다.

다음은 지불한 화폐와 구입한 물건의 가격을 입력받아 지불할 거스름 돈을 결정하는 함수입니다.

지불해야 할 거스름 돈을 계산합니다.

가장 큰 단위인 오만원보다 크면 오만원 권을 몇 개를 주어야 하는지 계산합니다.

다음 단위인 만원보다 크면 만원 권을 몇 개를 주어야 하는지 계산합니다. 이를 반복합니다.

이와 같은 알고리즘으로 문제를 해결하면 최소 개수로 잔돈을 지불할 수 있습니다.

▷ 실행 결과