[알고리즘] #01 그리디 알고리즘-거스름돈 문제

# 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

# 주로 정렬 알고리즘과 함께 나오는 유형

 

🛠 거스름돈 문제

🔧  문제 

 카운터에는 거스름돈으로 줄 수 있는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

---

🔧 아이디어

1) 거스름돈으로 줄 수 있는 단위 중 가장 큰 단위부터 돈을 거슬러준다.

- 이 문제 상황에서는 500원부터 거슬러 줄 수 있는 최대한으로 거슬러 준다. 

 

- 1260원을 거슬러줘야 한다고 가정해보자.

화폐단위	500	100	50	10
손님이 받은 개수	2	0	0	0

- 500원을 최대한 많이 거슬러줬을 때, 500원 2개를 손님에게 주었고 남은 거스름돈은 260원이다.  

 

다음으로 큰 단위는 100원인데, 남은 거스름돈이 100보다 크므로 100원으로 최대한 거슬러준다. 

거슬러 준 후의 결과는 다음과 같다.

화폐단위	500	100	50	10
손님이 받은 개수	2	2	0	0

- 손님에게 500원 2개, 100원 2개를 주어 총 1200원을 거슬러주었고 남은 거스름돈은 60원이다. 

 

다음으로 큰 단위는 50원이고, 남은 거스름돈이 50보다 크므로 50원으로 최대한 거슬러준다.

거슬러 준 후의 결과는 다음과 같다.

화폐단위	500	100	50	10
손님이 받은 개수	2	2	1	0

- 손님에게 500원 2개, 100원 2개, 50원 1개를 주어 총 1250원을 거슬러주었고 남은 거스름돈은 10원이다.

 

다음으로 큰 단위는 10원이고, 남은 거스름돈이 10보다 크므로 10원으로 최대한 거슬러준다.

거슬러 준 후의 결과는 다음과 같다.

화폐단위	500	100	50	10
손님이 받은 개수	2	2	1	1

- 손님에게 500원 2개, 100원 2개, 50원 1개, 10원 1개를 주어 총 1260원을 거슬러주었고 남은 거스름돈은 0이다.

 

남은 거스름돈이 0원이므로 거스름돈 문제를 마친다.

 

따라서 거스름돈이 1260원일 때, 손님이 받은 동전의 최소 개수는 6개가 된다.

---

🔧 코드 작성

# 거슬러 줄 돈 입력받기
n = int(input())

# 손님이 받을 동전의 수
count = 0

# 거슬러줄 수 있는 화폐의 단위를 담은 리스트
exchange = [500, 100, 50, 10]

for i in range(len(exchange)): # 리스트를 돌면서
    if (n >= exchange[i]): # 남은 거스름돈이 해당 화폐단위보다 큰지 확인
        count += n // exchange[i] 
        n = n % exchange[i];

print(count)