백준 파이썬 5585번: 거스름돈

www.acmicpc.net/problem/5585

5585번: 거스름돈

문제 유형: 그리디 알고리즘

 

# Solution 1

change = 1000 - int(input())
coins = [500, 100, 50, 10, 5, 1]

count = 0

for coin in coins:
    count += change // coin
    change %= coin # change = change % coin

print(count)

1. 1000원에서 입력 값을 뺀 나머지를 change 변수에 저장한다.
2. 잔돈을 큰 수부터 내림차순으로 정렬한 coins 배열을 만들어 준다. 큰 액수의 동전부터 거슬러주어야 최소한의 동전이 사용된다.
3. 반복문을 돌면서 동전의 총 개수 count에 change를 coin으로 나눈 몫을 더해준다.
4. change는 이전 단계의 나머지가 되고 그 나머지로 위의 과정을 반복한다.
5. 마지막으로 count를 출력해준다.