거스름돈

그리디 알고리즘

→ 매 순간 가장 좋아 보이는 것을 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다

→ '가장 큰/작은' 순서대로 같은 기준을 제시해줌

coin = int(input())  # 문제에선 1260원이라고 주어짐
money = [500, 100, 50, 10]
count = 0  # 거슬러줄 동전의 수
for c in money:
    count += coin//c
    coin %= c
    # print(str(c)+"원", count)
print(count)