백준 5585 (거스름돈) [Python/파이썬] [Greedy/그리디]

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

5585번: 거스름돈

 

---

나:

changes = [500,100,50,10,5,1]
count =0

money = 1000 - int(input())
for change in changes:
    count += money//change
    money = money%change
print(count)

완성된 코드는 위와같다. 

 

(1)
changes = [500,100,50,10,5,1]
count =0

잔돈의 총 종류 5개를 changes 리스트에 담아 나중에 활용하려고 함.

그리고 잔돈의 종류는 구분할 필요가 없이 그저 개수만 출력하면 되기 때문에 이를 한번에  나타낼 변수 count를 선언

 

(2)
money = 1000 - int(input())
for change in changes:
    count += money//change
    money = money%change
print(count)

문제에서 1000엔 지페를 한장 내고 받을 잔돈의 개수를 구하는 것을 전제로 했기 때문에 입력값에서 1000을 뺴줘야 함에 주의

언제나 거스름돈 개수가 가장 적게 잔돈을 줘야 함으로 큰 단위의 잔돈부터 줘야함을 알 수 있다. 이때 활용된 알고리즘을 그리디(greedy) 라고 볼 수 있다. 

각 단위의 잔돈별로 나오는 개수를 count에 추가하며 계산한 나머지를 그 다음 작은 단위의 잔돈으로 계산할 수 있게 나머지 값을 다시 moeny 에 넣는다. 결국 최종적으로 각 단위별 잔돈의 개수들이 모두 count 에 담긴다.

이후 그 최종 잔돈의 개수인 count를 출력한다.