[Python] SWEA D2 1970번 - 쉬운 거스름돈

SW Expert Academy

T = int(input())
change = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
for t in range(1, T + 1):
    n = int(input())
    chk = []
    for i in change:
        chk.append(n // i)
        n %= i
    print('#%d' % t)
    print(*chk)

- 거스름돈이 배수 관계를 이루는 전형적인 그리디 문제입니다.

- 그리디 문제는 나누어 주는 숫자끼리 배수 관계에 있을 때, 통하는 방법입니다. 서로 배수 관계가 아닌 경우에는 여러가지 케이스가 생길 수 있습니다.

- 각 거스름돈을 미리 저장한 리스트를 순회하며 입력된 금액을 거스름돈으로 나눈 몫이 거스름돈의 개수가 되고, 입력된 금액을 거스름돈으로 나눈 나머지가 그 다음으로 작은 단위의 거스름돈의 개수를 구하기 위한 수가 됩니다.

 

피드백은 언제나 환영합니다.