📌 문제 탐색하기
👉 문제바로가기
price: 타로가 지불할 돈(1<=N<=1000)
1000엔 을 냈을 경우 거스름돈에 포함된 매수를 구하는 문제입니다. 이 문제에서 잔돈의 단위는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔입니다. 거스름돈 개수가 가장 적게 잔돈을 주어야 하기 때문에 가장 큰 단위의 500엔으로 거스름돈을 줄 수 있는지부터 판단합니다. 이후 더 작은 돈의 단위로 가면서 잔돈을 지불합니다. 더이상 줄 돈이 없을때 종료하고 각 잔돈이 몇 매씩 필요한지 합해서 출력합니다.
📌 알고리즘 선택
Greedy Algorithm
그리디 알고리즘은 단순하면서도 강력한 문제 해결 방법입니다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘입니다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
가능한 시간복잡도
화폐의 종류만큼 반복을 수행하기 때문에 화폐의 종류가 N개일 때 코드의 시간 복잡도는 O(N)입니다. 이 문제에서는 화폐의 종류가 6개이므로 시간복잡도는 6이 되겠네요.
그리디 알고리즘의 정당성
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것이 아닙니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 큽니다.
하지만 이 문제에서처럼 당장 가장 큰 화폐 단위부터 돈을 거슬러주는 탐욕적인 방법으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있으면 매우 효과적이고 직관적인 방법입니다.
그리디 알고리즘으로 문제의 해결방법을 찾았을 경우 그 해법이 정당한지 검토해야합니다. 이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.
예를 들어 charge=800원이고 화폐단위가 인 경우 그리디 알고리즘으로는 500 1개, 100원 3개이지만 최적의 해는 400원 2개를 거슬러 주는 것입니다.
📌 코드 설계하기
- 지불할 돈과 돌려줘야 할 돈을 Input받습니다.
- 화폐의 단위를 리스트에 내림차순으로 저장합니다.
- 화폐의 단위를 큰 단위부터 불러와 각 화폐가 몇장 필요한지 구하고, 남는 돈은 더 작은 단위의 화폐 단위를 이용해 매수가 몇 장 필요한지 구하는 방식으로 반복문을 수행합니다.
- 총 매수를 출력합니다.
📌 정답 코드
import sys
price = int(sys.stdin.readline())
charge = 1000 - price
yen = [500, 100, 50, 10, 5, 1]
cnt = 0 #잔돈 매수
sum = 0 #잔돈 매수의 합
for i in yen:
if charge == 0:
break
cnt = charge // i
sum += cnt
charge = charge % i
print(sum)
📌 참고자료
- 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈, 한빛미디어
- 탐욕 알고리즘(Greedy Algorithm)_ssokeem님의 velog
- Greedy Algorithm (그리디 알고리즘)_by 걸어가는 신사
- https://ssdragon.tistory.com/114
