교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 3 그리디
예제 3-1 거스름돈 87p
백준 BOJ 5585 거스름돈
문제
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.
입력
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
출력
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
풀이
접근 1
- 1000 - 입력값
- 큰 잔돈부터 돌리기
Note
- for문에 넣기 위해 배열에 잔돈 저장하기
제출 1 - 정답
pay = int(input())
left = 1000-pay
money = [500,100,50,10,5,1]
cnt=0
for i in money:
while left >= i:
left -= i
cnt+=1
print(cnt)
오답노트
교재에 있던 솔루션은 돈을 잔돈으로 나눈 "몫(//)"을 count하고 "나머지(%)"를 돈으로 저장했다...
짧은 코드지만 이렇게 시간 아낄 수 있도록 깔끔하게 생각할 수도 있구나 했당... 바보수진... 아무래도 책 참 잘산 것 같다
그리고 800원을 거슬러 줄 때 화폐단위가 지금처럼 배수가 아니라 무작위로 500 400 100이라면 500+100+100+100으로 거슬러주겠지만 400+400이 가장 효율적일거기 때문에 그리디가 아닌 다른 알고리즘을 사용해야한다는 언급이있는데.. 정말 책을 여러가지 생각하면서 꼼꼼하게 만드신 걸 알 수 있었다..ㅠㅠ 이런 거까진 깊게 생각 안해봤는데 그냥 나도 그리디로 풀다가 갑자기 안되면 다른 알고리즘 써야겠다 생각했을듯... 문제 만났을 때 풀이 법을 좀 더 잘? 생각하는 루트를 만들 수 있게 노력해야겠다
- 책에 있는 솔루션
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)결과
- 풀이시간 : 5분
- 메모리 : 121220KB
- 시간 : 112ms
References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저
