그리디-거스름돈

이 문제는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

 

for coin in coin_types:#coin_types는 잔돈 동전의 모음
	count += n#count는 받는 동전 수, n은 입력값
    n %= coin

이렇게 하면 코드의 시간 복잡도는 O(K)이다. 이 알고리즘은 동전의 종류(coin_types)에만 영향을 받고 거슬러 줘야하는 금액의 크기와는 무관하다.