[SW Academy] 1970. 쉬운 거스름돈

📖 문제

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

우리나라 화폐 ‘원’은 금액이 높은 돈을 우선적으로 계산할 때 돈의 개수가 가장 최소가 된다.

S마켓에서 사용하는 돈의 종류는 다음과 같다.
50,000 원
10,000 원
5,000 원
1,000 원
500 원
100 원
50 원
10 원

S마켓에서 손님에게 거슬러 주어야 할 금액 N이 입력되면 돈의 최소 개수로 거슬러 주기 위하여 각 종류의 돈이 몇 개씩 필요한지 출력하라.

[예제]

N이 32850일 경우,
50,000 원 : 0개
10,000 원 : 3개
5,000 원 : 0개
1,000 원 : 2개
500 원 : 1개
100 원 : 3개
50 원 : 1개
10 원 : 0개

[제약 사항]

1. N은 10이상 1,000,000이하의 정수이다. (10 ≤ N ≤ 1,000,000)

2. N의 마지막 자릿수는 항상 0이다. (ex : 32850)

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스에는 N이 주어진다.

[출력]

각 줄은 '#t'로 시작하고, 다음줄에 각 돈의 종류마다 필요한 개수를 빈칸을 사이에 두고 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

📖 풀이

그리디 알고리즘으로 유명한 거스름돈 나누어주기.
큰 액수 순으로 나누어주어 거슬러주면 된다.

*문제에 오류가 있는데, 제한 조건에 N의 마지막 숫자가 0이라고 명시되어있는데, 들어오는 input값은 조건에 위배된다. (ex: 99999)
이 부분 때문에 자꾸 틀리다고 나와서 좀 헤맸다;;

그냥 0의 자리수를 따로 버려주면 된다.

T = int(input())
money_arr = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    money_dic = {50000: 0, 10000: 0, 5000: 0, 1000: 0, 500: 0, 100: 0, 50: 0, 10: 0}
    N = int(input())

    if N % 10 != 0:   # input N의 일의 자리 수가 0이 아닐 때 일의 자리 수를 버림.
        N = N // 10 * 10

    while N != 0: # 거슬러주는 파트
        for i in money_arr:
            if N // i != 0:
                money_dic[i] += N // i
                N -= i * (N // i)

    a = list(money_dic.values())
    print("#{0}".format(test_case))
    for i in a:
        print(i, end = ' ')
    print('')