[SWEA]1970.쉬운 거스름돈

1970.쉬운 거스름돈

문제

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

50000원, 10000원, 5000원, 1000원, 500원, 100원, 50원, 10원이 있다면 만원을 주는 방법은 10000원권 하나혹은 오천원권 두장천원권 세 장등이 있겠습니다. 그래서 높은 금액 수를 먼저 계산하는것이 거스름돈의 개수를 최소로 주는 방법입니다.

N원이 입력 됐을때 거스름돈의 갯수를 최소로 돌려주기 위해 각 종류의 돈이 몇 개씩 필요한지 나타내보세요.

제약 사항

N의 마지막 자릿수는 항상 0입니다.

출력 예시

N이 32850일때,

#1 0 3 0 2 1 3 1 0

---

생각해보기

우선 N이 주어지면 50000원이 넘는지 판단하고 넘는다면 나누기해서 몫으로 몇개가 나오는지 판단하고 그 몫 곱하기 50000을 제외한 금액을 계산한 나머지 잔돈에 또 해줍니다.

그렇다면 돈 단위를 리스트로 만들어서 나누고 그 값을 따로 저장하고 N을 새로 정의해주면서 새로 정의된 N에 계산하도록 만들어 봐야겠습니다.

풀어보기

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    won = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
    rest = []
    for i in won:
        rest.append(str(N//i))
        N = N - (N//i)*i
    print(f"#{tc}\n{' '.join(rest)}")