[그리디 알고리즘] 5585번 - 거스름돈

[백준] 5585번 - 거스름돈

1) 문제 해결 아이디어

그리디 알고리즘의 대표적인 문제이다.

for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다.

 

2) 소스코드

pay = int(input()) # 지불 금액
money = [500, 100, 50, 10, 5, 1]
charge = 1000 - pay  # 잔돈
res = 0  # 잔돈 개수

for m in money:
  # 탈출 조건
  if(charge == 0):
    break
  # 해당 단위로 나눠지면
  if((charge // m) != 0):
    res += charge // m  # 잔돈 개수 추가
    charge %= m    # 잔액 변경
    
print(res)