[SWEA] 1970. 쉬운 거스름돈 (Python/D2)

SW Expert Academy

---

설명

거스름돈을 최소 화폐로 거슬러줘야 한다. 돈의 종류는 아래와 같이 존재한다.

50,000 원, 10,000 원, 5,000 원, 1,000 원 , 500 원, 100 원, 50 원, 10 원

 

풀이

그리디 알고리즘이다. 단순 구현 문제이다.

 

1. 화폐의 종류를 한 리스트에 저장한다.

2. 반복문으로 리스트를 돌린다.

3. 거스름돈을 화폐의 종류 중 하나로 나눈 몫을 따로 저장한다.

• 만약 거스름돈이 32850원일 때, 나눌 수 있는 제일 큰 화폐는 10000원이다.
• 10000원으로 나눈 몫은 3이다. 즉, 3장의 10000원으로 거슬러 줄 수 있다는 말이다.

4. 거스름돈을 나눈 나머지를 다시 거스름돈 변수에 저장한다.

• 거슬러주고 남은 돈은 또 다른 작은 화폐로 거슬러 줄 수 있으므로 거스름돈 변수에 나머지를 저장한다.
• 위에서 10000원으로 나눈 나머지는 2850원이고, 다시 반복문을 돌린다.
• 10000원 다음은 5000원(i)인데 5000원이 거스름돈보다 크므로 거슬러 줄 수 없으므로 다음 i인 1000원으로 넘어간다.
• 이런식으로 반복한다.

5. 몫을 출력하고 위 과정을 반복한다.

 

 

Solution

t = int(input())
money = [50000, 10000, 5000, 1000, 500, 100, 50, 10]

def calc(n):
    for i in money:
        ans = 0
        if n >= i:
            ans = n // i #화폐 개수 (32850 / 10000 = 3)
            n %= i # 거슬러주고 남은 돈 (n = 2850) 
        print(ans, end= " ")

for i in range(1, t+1):
    n = int(input()) #거스름돈
    print("#"+str(i))
    calc(n)
    print() #다음 입력을 위해

---

👩‍💻 회고

그리디는 백준에서 많이 풀었던 문제라서 어렵지 않게 풀 수 있었다. 다만 처음엔 리스트에 화폐를 저장하지 않고 5와 10으로 나누면서 풀려고 했는데 복잡해져서 어떻게 풀어야 하나 걱정이었다. 다행히도 리스트에 저장해놓고 반복문을 돌리면서 푸는 방법이 기억나서 이후부터는 구현도 문제 없었고, 첫 제출에 바로 패스했다.