백준 2720번: 세탁소 사장 동혁 - 파이썬

 

코드

'''
세탁소 사장 동혁
https://www.acmicpc.net/problem/2720
'''

t = int(input())
m = [25,10,5,1]


for _ in range(t):
  result = []
  n = int(input())

  for i in m:
    result.append(str(n//i))
    n %= i
  
  print(' '.join(result))

 

해설

이 문제는 그리디 문제이다. 그리디하게 가장 단순하게 생각해서 최대한 적게 주어야 한다면 가장 큰 단위를 최대한 많이 주는 것이다.

예를들어 돈의 단위가 10과 1이 있다고 해보자 거슬러 주어야 할 돈이 20이라 해보자.

 

최대한 적게 주어야 한다면 10을 최대한 많이 주어야 한다. 따라서 10을 2개주면 된다.

 

이에따라 결론을 내리자면 

거스름돈이 총 25, 10, 5, 1 이 있다면 가장 액수가 큰 단위 부터 차례로 거스름돈을 나누면 된다.

 

 

그리디 알고리즘의 정당성

 

금액의 크기가 큰 것부터 차례대로 거스름돈 계산을 할 때 25, 10, 5, 1의 경우 최저 거스롬돈이 보장된다.

만약 25, 20, 5, 1 이라고 했을때 이대로 계산하는 것은 최저 거스름돈을 보장해주지 않는다. 왜냐하면 만약 

40 센트를 거슬러 주어야 한다면 

 

1, 0, 3, 0  이라는 결과가 나올 것이다. 하지만 정답인 최저 거스름돈은 0, 2, 0, 0 이 되어야 한다.

 

25, 10, 5, 1 의 경우는 10이 아닌 다른 것들을 이용하면 최저를 만들수 있지만 25, 20, 5, 1의 경우는 40 이상의 수부터 20을 쓰는 경우만이 최저인 경우가 있기 때문이다. 

 

즉 거스름돈이 어떻게 구성되었는지에 따라 위 같은 풀이가 맞을 수도 있고 틀릴 수도 있는 것이다.