[백준 5585번] 거스름돈 - 파이썬

문제 링크:

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

• 거스름돈 = 1000엔 - 입력값
• 거스름돈이 작은 수의 배수만큼 있으므로 큰 동전부터 거슬러주면 된다. (그리디 알고리즘의 최적의 해)
• 동전들의 종류 리스트인 coins를 만들어 큰 동전부터 차례대로 개수를 세주면 된다. 

 

<풀이>

# 5585번 거스름돈

#1. 500엔부터 순차적으로 거스름돈을 주면 된다.

n = int(input())

# 거스름돈
money = 1000 - n

# 동전의 종류
coins = [500, 100, 50, 10, 5, 1]

# 거스름돈 동전의 개수
cnt = 0 

# 동전 거슬러 주기
for coin in coins:
  cnt += money // coin 
  money %= coin
 
print(cnt)

 

[백준 5585번] 거스름돈 - 파이썬