[그리디]백준 5585 거스름돈 | 파이썬 풀이

문제 링크

• https://www.acmicpc.net/problem/5585

1. 문제 설명

어느 상점에서 1000엔짜리 지폐 한 장으로 물건을 산다고 했을 때, 받을 거스름돈의 최소갯수를 구하는 문제이다.
받을 수 있는 잔돈의 단위는 500 100 50 10 5 1 총 6개이다.

예를들어 750엔어치 물건을 산다면 250엔이 거스름돈이 될 것이고, 250엔은 100엔짜리 두개, 50엔짜리 한개로 총 세개의 잔돈이 생겨 3을 출력하면 정답이 된다.

2. 문제 풀이

이 문제는 그리디하게 접근해보면, 제일 큰 단위의 잔돈으로 거스름돈을 채워나갈 때 잔돈의 갯수가 최소가 될 것이다. 따라서 코드로 500엔짜리부터 몇개가 들어가고 남은 돈은 100엔짜리로 채우는 등의 로직을 작성하면 되는 간단한 문제였다.

처음 작성한 코드는 이렇다.

# total_pay : 물건의 총 금액
# remain_money : 1000엔에서 뺀 남은 금액
# ans : 정답을 저장할 변수

total_pay = int(input())
remain_money = 1000-total_pay

ans = 0
ans += remain_money // 500
remain_money = remain_money % 500

ans += remain_money // 100
remain_money = remain_money % 100

ans += remain_money // 50
remain_money = remain_money % 50

ans += remain_money // 10
remain_money = remain_money % 10

ans += remain_money // 5
remain_money = remain_money % 5

ans += remain_money // 1
remain_money = remain_money % 1

print(ans)

생각나는 대로 써보기도 했고, 파이썬에 익숙하지 않아 코드가 좀 보기싫은? 상태였다. 다른 사람들의 코드를 보니 매우 간단하게 짤 수 있었다.

# total_pay : 물건의 총 금액
# remain_money : 1000엔에서 뺀 남은 금액

total_pay = int(input())
remain_money = 1000-total_pay

a = remain_money//500 # 500엔으로 낼 수 있는 갯수 저장
b = remain_money%500//100 # 500엔을 다 내고 난 후 100엔으로 낼 수 있는 갯수 저장
c = remain_money%100//50 # 100엔을 다 내고 난 후 50엔으로 낼 수 있는 갯수 저장
d = remain_money%50//10 # 반복
e = remain_money%10//5 
f = remain_money%5

print(a+b+c+d+e+f)

로직의 의미는 살짝 다르지만, 이 문제의 특성상 필요한 50엔의 갯수를 구할 때 500엔으로 나눈 나머지나 100엔으로 나눈 나머지나 같은 결과를 의미하므로 결과는 같다.