그리디 알고리즘 기초 - 거스름돈

그리디 알고리즘은 "현재 상황에서 지금 당장 좋은걸 고르는 방법" 을 이용한 알고리즘이다

 

대표적인 문제로 거스름돈 문제가 있다

 

동전의 갯수를 최소화하여 돈을 거슬러 주는 문제이다

 

거스름 돈을 줄때에 제일 큰 금액부터 거슬러 주면 성립이 된다

 

#greedy 의 대표 문제 거스름돈

money = int(input())
count = 0
coins = [500,100,50,10]

for i in coins:
    count += money // i
    money %= i
    
print(count)