Programming/SW Expert Academy
20210115 // 삼성 SW Expert 아카데미 // 1970
껨코
2021. 1. 15. 16:35
삼성 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원을 빼준다.
이러한 방식으로 다 빼주면서 동전 수 리스트에 하나씩 담으면 된다.
또한 이 알고리즘은 그리디 알고리즘(탐욕 알고리즘)의 방식 중 하나로 그때그때 최선의 방식을 선택하는 알고리즘 종류 중에 하나이다.