이것이 코딩테스트다 -그리디

3-1 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 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)

정당성 검토

예를 들어 800원을 거슬러 줘야 할 때, 화폐 단위가 500원, 400원, 100원인 경우 그리디 알고리즘으로는
500원 + 100원 + 100원 + 100원으로 4개의 동전으로 나오게 되는데, 최적의 해는 400원, 400원 으로 2개의 동전이다.


항상 문제를 풀고 난 뒤 정당한지 검토하는 습관을 들이도록 노력하자