20210115 // 삼성 SW Expert 아카데미 // 1970

삼성 SW Expert 아카데미 1970번 "쉬운 거스름돈" 문제입니다.

TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    money = [50000, 10000, 5000, 1000,500, 100, 50, 10]
    coin = []
    for i in range(len(money)):
        coin.append(N//money[i])
        N %= money[i]
    print("#%s"%tc)
    for ele in coin:
        print(ele, end=" ")
    print()

유명한 거스름돈 문제이다. 돈의 액수가 주어지고 그 돈만큼 돈을 거슬러줘야 하는 문제이다.

 

거스름돈 액수에서 뺄 수 있는 돈의 단위가 큰 단위부터 빼준다. 예를 들어 32850원이 입력값으로 들어갔을 때

 

5만원은 뺄 수 없으므로 그 다음 뺄 수 있는 돈의 단위는 1만원이므로 1만원을 3장까지 뺄 수 있으므로(나눗셈 연산자 이용) 3만원을 빼준다.

 

그 다음은 2850원이 남는데 5000원은 뺄 수 없으므로 1000원을 2장까지 뺄 수 있으므로 2000원을 빼준다.

 

이러한 방식으로 다 빼주면서 동전 수 리스트에 하나씩 담으면 된다.

 

또한 이 알고리즘은 그리디 알고리즘(탐욕 알고리즘)의 방식 중 하나로 그때그때 최선의 방식을 선택하는 알고리즘 종류 중에 하나이다.