그리디 거스름돈

from 이것이 코딩테스트다 with 파이썬 학습기록

 

거슬러줘야 할 동전의 최소 개수

n = 1260 # 금액
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin

print(count)

시간복잡도 O(K)

동전의 총 종류에만 영향, 거슬러 줘야 하는 금액의 크기와는 무관

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위 동전들을 종합해 다른 해가 나올 수 없음