[SWEA] 1970 | 쉬운 거스름돈

문제링크

---

1970 | 쉬운 거스름돈

풀이과정

---

동전 거슬러주기는 대표적인 그리디 알고리즘의 예시이다.
[BOJ] 세탁소 사장 동혁, [Softeer] 금고털이 와 같은 문제들이 있다.

잔돈 배열을 만들어주고, for문으로 잔돈 배열을 돌아보자.
현재의 잔돈으로 값을 거슬러줄 수 있는 값이 있다면, 즉 N이 현재의 잔돈으로 나눠진다면 결과값을 잔돈 개수만큼 올려주면 된다.

나머지 금액은 for문을 돌고있으니까 다음 잔돈으로 짤짤이 되겠지 ~

코드

---

T = int(input())

changes = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
for tc in range(1, T+1):
    result = [0] * 8
    N = int(input())

    for i in range(len(changes)):
        cnt = N // changes[i]
        if cnt > 0:
            N = N % changes[i]
            result[i] = cnt

    print(f'#{tc}')
    print(*result)

결과

---