[백준/python] 2720 세탁소 사장 동혁: 거스름돈 계산 -> 그리디 알고리즘이 왜 가능할까?

 

import sys

n=int(input())
arr=[25, 10, 5, 1]
result=[0]*4

for i in range(n):
  j=0
  c=int(sys.stdin.readline())
  while(j!=len(arr)):
    result[j]= c//arr[j]
    c=c%arr[j]
    print(result[j],end=' ')
    j+=1
  print()

 

 

궁금한 점 1: 1과 5는 배수가 되는데 10은 25의 배수가 될 수 없다. 그런데도 큰 단위 화폐부터 돈을 거슬러주는 그리디 알고리즘이 통하네??

 

500원, 100원, 50원, 10원 동전으로 생각해보자. 이들은 모두 작은 단위의 화폐를 종합해 큰 단위의 화폐를 만들 수 있다. 즉, 서로 배수 형태라는 말이다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 잇는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

 

참고로 화폐 단위가 서로 배수가 아니라 무작위로 주어질 경우 다이나믹 프로그래밍으로해결할 수 있다.

그런데 위의 경우는 10의 배수가 25가 될 수는 없다. 그럼에도 그리디 알고리즘 적용이 가능한지 파악하는 방법이 뭘까?..??????