[그리디 / python] 거스름돈

문제풀이

n=int(input())
count=0
coin_types = [500,100,50,10]

for coin in coin_types:
    count+=n//coin
    n%=coin

print(count)

 

*그리디 알고리즘 적용이 가능한 이유

가지고 있는 동전 중, 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다!