백준 5585번 거스름돈 (Python)

출처

백준 5585 거스름돈

---

정답

import sys 

coins =  [500, 100, 50, 10, 5, 1]
N = int(sys.stdin.readline())
changes = 1000 - N 

coins.sort(reverse=True)
count = 0
for coin in coins:    
    count += (changes // coin)
    changes = changes % coin

print(count)

---

문제

---

입출력

---

풀이

0. 전략

위키백과-탐욕_알고리즘

탐욕(Greedy) 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다

큰 동전은 모두 작은 동전의 배수이다 [500엔, 100엔, 50엔, 10엔, 5엔, 1엔]
그러므로 거스름돈을 모두 지불할 때까지 선택할 수 있는 가장 큰 동전부터 거슬러주면 최적해를 구할 수 있다 

1. 문제/입력값에 의한 초기 설정

# 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고
coins =  [500, 100, 50, 10, 5, 1]
# 지불한 돈 입력 
N = int(sys.stdin.readline()) # 380
# 거스름돈 계산 
changes = 1000 - N  # 620

2. 거스름돈 동전 세기 알고리즘

# 가장 큰 순으로 동전을 정렬 
coins = coins.sort(reverse=True)
# 거스름돈으로 사용한 동전개수 초기값 
count = 0
# 거스름돈의 개수 만큼 반복 처리 : 6회 
for coin in coins:    
    # 가장 큰 동전으로 나눈 몫을 동전 개수에 추가
    count += (changes // coin)  # 620 // 500 = 1
    # 거스름돈은 가장 큰 동전으로 나눈 나머지로 수정 
    changes = changes % coin # 120

3. 정답 출력

# 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
print(count)

---

반복 회차별 거스름돈 및 동전 개수 상태

1) 320엔

회차	거스름돈	동전개수 및 나머지
1회	620원	500원 * 1개 및 120원
2회	120원	100원 * 1개 및 20원
3회	20원	50원 * 0개 및 20원
4회	20원	10원 * 2개 및 0원
5회	0원	5원 * 0개 및 4원
6회	0원	1원 * 0개 및 0원

동전개수 = 500원 1개, 100원 1개, 10원 2개 = 4개

2) 1엔

회차	거스름돈	동전개수 및 나머지
1회	999원	500원 * 1개 및 499원
2회	499원	100원 * 4개 및 99원
3회	99원	50원 * 1개 및 49원
4회	49원	10원 * 4개 및 9원
5회	9원	5원 * 1개 및 4원
6회	4원	1원 * 4개 및 0원

동전개수 = 500원 1개, 100원 4개, 50원 1개, 10원 4개, 5원 1개, 1원 4개 = 15개

---