[그리디 알고리즘] - 거스름돈

✈그리디 알고리즘 (Greedy Algorithm) - 거스름돈

★ 그리디 알고리즘이란?

👀 문제 설명

• 🙎‍♂️ 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요.
• 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

---

👀 문제 해결 아이디어

• 최소 개수를 구하기 위해선 가장 큰 화폐 단위부터 거슬러 주면 된다.

---

👀 소스 코드

n = int(input())  # 거슬러 주어야 할 돈

change_list = [500, 100, 50, 10]  # 거스름돈 목록

count = 0  # 동전의 최소 개수

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

print(count)