백준 5585번 거스름돈 문제 풀이 Python

문제 정의

거스름돈 문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력: 물건의 가격

출력: 최소 잔돈의 개수

---

문제 해석

가지고 있는 6종류의 잔돈을 사용하여, 거스름돈의 개수가 가장 적게 하는 해를 구해야 함. 가장 적게 하기 위해서는 큰 단위의 돈을 최대한으로, 작은 단위의 돈을 최소한으로 전달해야 함.

 

잔돈을 내림차순으로 정렬한 뒤, 거스름돈을 나눈 몫을 잔돈의 개수에 더하고, 나머지를 새로운 거스름돈으로 할당함. 이 과정을 반복하다가 거스름돈이 0이 되면 loop를 멈추고 결과를 리턴한다.

 

본 문제는 가장 간단하고 대표적인 greedy 알고리즘의 예시이다(동빈 나의 알고리즘 강의 참고). 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 알고리즘이다. 문제를 접하였을 시, 해당 문제가 상황에서 당장 좋은 것만을 골라도 최적의 해를 도출할 수 있을지 그 정당성을 분석하는 것이 매우 중요하다. 이 문제의 경우, 주어진 잔돈의 종류가 500, 100, 50 등 큰 단위가 작은 단위의 배수로 구성되어 있다. 때문에 작은 단위의 잔돈을 종합해도 큰 단위의 잔돈 개수보다 작은 해를 찾을 수 없다. 따라서 당장 좋은 것(가장 큰 단위의 잔돈부터 사용하는 것)을 고르는 것이 최적의 해에 도달하는 방법이다.

---

시간 복잡도 Big-O

잔돈의 종류 수를 K(위에서는 6)라고 할 때, 거스름돈의 크기와는 상관 없이 O(k)의 시간복잡도를 가질 것.

그리 복잡하지 않고, 더 이상 효율적이기도 어려움.

---

구현

# 거스름돈
charge = 1000-int(input())
num_coins = 0

for c in [500, 100, 50, 10, 5, 1]: # 잔돈 내림차순으로 배열
    num_coins += charge//c
    charge %= c
        
# 잔돈의 개수 출력
print(num_coins)

• 메모리: 31256 KB
• 시간: 44 m

원래는 for loop 내에 거스름돈이 0보다 작거나 같아지면 멈추게 하는 코드가 있었는데( if~break), 그 문장을 제거하니 오히려 시간이 줄어들어서 제거하였다. 해당 파이썬 파일은 github 링크에서도 확인할 수 있다.