Ex. 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
해설
⇒ 핵심은 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)6그리디 알고리즘의 정당성
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제가 그리디로 해결되는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예로 800원을 거슬러 줘야 하는데, 화폐 단위가 500·400·100원인 경우에 그리디 알고리즘으로는 4개의 동전(500원 + 100원 x3)을 거슬러 줘야 한다고 나오지만 최적의 해는 2개의 동전(400원 x2)이다.
