[BOJ][Python]5585 풀이

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

5585번: 거스름돈

price = int(input())
change = 1000 - price
ans = 0
coin = [500, 100, 50, 10, 5, 1]
for i in coin:
    coin_num = change // i
    change -= i*coin_num
    ans += coin_num
print(ans)

이번 문제는 그리디 알고리즘의 대표적인 문제 중 하나인 동전 갯수 문제입니다. 잔돈이든 목표액이든 무게든 뭐 여러가지 변형은 있을 수 있지만 다 똑같은 문제로 봐도 무방합니다.

 

그리디 알고리즘의 특징은 매순간마다 최적의 선택을 하는 것이죠. 현재의 선택이 나중의 선택에 영향을 미치지 않을수록 쉬운 그리디 문제로 분류됩니다. 특히 지금같은 동전 갯수 문제가 그러하죠. 갯수의 제한도 없고 지금 금액이 큰 동전을 선택한다고 해서 나중에 다시 처음으로 돌아와서 큰 금액을 빼고 작은 걸 하나 더 넣는 등의 일을 할 필요 없이, 매순간 최대한 큰 금액을 만들면 결국 그게 가장 적은 갯수의 동전으로 이어지는 간단한 문제입니다.

 

나름 핵심이라면 몫 연산을 사용해서 조건문을 사용하지 않고 동전의 배열만 다 돌면 되게끔 만들었다는 점이 있겠습니다. 뺄셈으로 하게되면 거스름돈이 0보다 커야한다는 조건을 사용해야하는데 몫 연산으로 구하면 거스름돈의 총액이 i(동전 금액)보다 작으면 몫이 0이 되므로 조건문을 사용해야할 이유가 없죠. 물론 조건문까지 사용해서 타이트하게 짠 코드보다는 불필요한 연산이 생깁니다(예를 들어 거스름돈이 1엔이어도 500, 100, 50... 하나씩 다 몫 연산을 해야하기 때문).

 

재귀로도 풀 수 있지만 반환값이나 파라미터를 고려하다보면 그리디가 낫구나 하는 생각이 드실겁니다.