[백준] 거스름돈 파이썬

 

 

5585번: 거스름돈

 

문제 접근

큰 단위의 거스름돈으로 먼저 최대한 바꿔줄 수 있는 수량을 파악해야했다. 거스름돈 종류는 이미 순차적으로 제공되었다.

 

알고리즘

그리드 알고리즘

 

풀이 과정

cnt = 0
price = int(input())
change = 1000 - price
money = [500, 100, 50, 10, 5, 1]

while change > 0:
  for m in money:
    if (change // m) > 0:
      cnt += 1
      change = change - m
    else:
      continue

이렇게 코딩을 처음에 했으나 제대로 된 답이 나오지 않았다. 원인은 for 루프를 통해 무조건 cnt 를 +1 씩 올리는 것 때문이다. 예를 들어 거스름돈이 50원이고 10원으로 5개로 나누어 주면 되는데 cnt +1 올리고 다음 5원으로 넘어가니 cnt가 많이 추가된다. 따라서 아래와 같이 코드를 바꿨다.

 

cnt = 0
price = int(input())
change = 1000 - price
money = [500, 100, 50, 10, 5, 1]

for m in money:
  cnt += change // m
  change = change % m

루프는 1회만 돌며 큰 단위서 부터 최대한 바꿔줄 수 있도록 하였다.