[Python] 백준/BOJ - 5885번: 거스름돈

5585번: 거스름돈

문제

타로는 잡화점에서 물건을 산다. 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 잡화점에서 물건을 계산할 때 1000엔 지폐를 한 장 냈을 때, 받을 잔돈의 개수를 구하시오.

 

입력

타로가 지불할 돈(구매할 상품의 가격)(1이상 1000미만의 정수)

 

출력

잔돈에 포함된 매수

 

 

예제 입력 1

380

 

예제 출력 1

4

 

예제 입력 2

1

 

예제 출력 2

15

 

풀이

전형적인 그리디 알고리즘을 이용하여 푸는 문제이다.

 

pay = int(input())
cnt = 0
coins = [500, 100, 50, 10, 5, 1]
n = 1000 - pay # 잔돈 계산

for coin in coins: # 큰 돈부터 차례대로 확인
    cnt += n // coin
    n %= coin

print(cnt)

 

먼저 가지고 있는 거스름돈의 종류들을 리스트에 넣어준다. 그리고 나서 타로가 낸 돈에서 상품 가격을 빼서 잔돈을 얼마나 줘야하는지 계산한다.

 

for문을 coins에 있는 큰 단위의 돈부터 확인하며 돌아준다. cnt에는 n // coin을 넣어주면 되는데 이렇게 하면 그 돈을 몇개를 거슬러줄지 알 수있게 된다.

예를 들어 거슬러줄 돈이 1200원이고 500원으로 나눠주면 1200 // 500은 2로, 500원 2개를 거슬러주는 것이다.

 

이를 cnt에 더해준 뒤에는 n을 coin으로 나눈 나머지를 n에 넣어주면 된다.

이것도 예를 들어보면, 1200 % 500을 해주면 200으로, 500원으로 줄 수있는 잔돈을 모두 주고난 뒤 남은 돈이 다시 n에 들어가는 것이다.

 

끝!