백준 5585: 거스름돈 (Python)

알고리즘/백준

sssbin 2021. 9. 29. 14:28

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

n = int(input())

cash = [500, 100, 50, 10, 5, 1]
k = 1000 - n
cnt = 0

for i in cash:
    cnt += k // i
    k %= i

print(cnt)

그리디 알고리즘을 거스름돈 문제를 예시로 들어서 공부했기 때문에 쉽게 풀 수 있었다!