문제 설명
어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.\
거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.\
예를 들어 54520원인 경우,\
거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.\
(※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)
입력
거스름돈 n이 입력된다. ( n은10이상의 int 범위 )
출력
최소 거스름돈의 개수를 출력한다.
입력 예시
54520
출력 예시
8
문제 풀이
전체 코드
change = int(input())
changeCount = 0
moneyList = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
for money in moneyList:
changeCount = changeCount + (change // money)
change = change % money
print(changeCount)탐욕법 문제 중 단골로 나오는 거스름돈 문제이다.
핵심은 주어진 화폐로 거슬러 줄 돈을 나눈 나머지와 몫이 중요하다.
먼저 주어진 금액을 확인 한 후 가장 큰 금액부터 거슬러준다. 이렇게 해야 가장 최소 단위로 돈을 거슬러줄 수가 있다.
만약 거슬러줄 돈이 위에 처럼 54520원이라면
1) 제일 큰 50000원 먼저 거슬러준다. -> 총 거스름돈 개수 1, 남은 금액 4520원
2) 거스름돈이 10000원보다 작으므로 Pass.
3) 마찬가지로 5000원보다 작으므로 Pass.
4) 4520원이므로 1000원 4장을 거슬러준다. -> 총 거스름돈 개수 5, 남은 금액 520원
5) 520원이므로 500원 1개를 거슬러준다. -> 총 거스름돈 개수 6, 남은 금액 20원
6) 남은 금액이 100원, 50원보다 작으므로 Pass.
7) 20원을 거슬러주기 위해 10원 2개를 거슬러준다. -> 총 거스름돈 개수 8, 남은 금액 0원
이렇게 거슬러주면 가장 최소 개수로 거스름돈을 거슬러줄 수 있다.
난 먼저 금액 단위가 정해져 있으므로 해당 금액들을 배열로 만들어주었다.
moneyList = [50000, 10000, 5000, 1000, 500, 100, 50, 10]그 후 50000원 부터 10원까지 가장 최소 단위로 계속 돌면서 거스름돈 개수를 계산해야 하기 때문에
위의 리스트를 반복문을 돌리면서 몫과 나머지를 구해줬다.
changeCount = 0
for money in moneyList:
changeCount = changeCount + (change // money)
change = change % money거슬러줄 돈 changeCount를 최초 0으로 초기화해준 후 moneyList를 for문으로 돌려준다.
반복문을 돌면서 거슬러줄 돈을 50000원권 부터 순서대로 나눈 값의 몫을 changeCount에 저장해준다.
changeCount는 몫이 생길때마다 카운트가 늘어나게 된다.
그리고 거스름돈은 금액을 나누고 남은 나머지값이 남은 거스름돈이 되므로 다시 세팅을 해준다.
그리고나서 나온 최종 changeCount가 거슬러 줘야할 거스름돈의 최소 개수가 된다.
문제 회고
저번에 풀었던 리모컨 문제보다는 훨씬 쉽게 풀 수 있었다.
어떻게보면 몫과 나머지를 갖고 푸는게 저번 문제와 거의 유사한 느낌도 들긴 했다.
'큰 금액 부터 처리해 나가면서 거스름돈 개수를 체크하면 가장 최소가 될 수 있겠다' 를 기준으로 잡아서 50000원 거슬러주는 것부터 풀어 나갔다.
주어진 금액에서 50000원을 나누니 몫 1과 나머지 4520원이 나왔고, 보니까 나머지 값이 54520-50000=4520 과 똑같았다.
결국 몫은 줘야할 50000원권 1장인 것이다.
그래서 어짜피 거슬러줘야할 금액 단위들은 정해져 있으므로 리스트로 만들어서 반복문으로 처리할 수 있도록 처리했다.
고민했던 거에 비해 금방 풀린 문제!
