Coding Test

[백준] 거스름돈

상상쓰 2021. 6. 4. 11:12

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

 

5585번: 거스름돈

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

www.acmicpc.net

 

백준에서는 당분간 그리드 알고리즘 위주로 풀어볼 생각이다.

가장 큰 화폐부터 거스름돈을 계산해서 주면 된다.

 

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

for i in change:
    answer = answer + (M // i)
    M = M % i
    
    if M == 0:
        print(answer) # 4
        break