본문 바로가기

백준 write-up/정렬 & 그리디

[백준] 거스름돈 : 5585번 - Python

728x90
반응형

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

 

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

 

 

 

https://ye5ni.tistory.com/66  ===> 참고

 

 

 

문제의 접근 방법

 

- 거스름돈 개수가 가장 적게 잔돈을 주려면 잡화점에서 가지고 있는 잔돈을 가장 큰 단위부터 거슬러주어야 함.

- 타로는 1000엔 지폐를 한 장 냈기 때문에 1000엔에서 타로가 지불해야 할 돈을 빼준 값이 받아야할 잔돈의 값을 의미함.

 

 

 

문제 풀이 방법

 

타로가 지불해야 할 돈 N엔 입력받기 -> 잡화점에서 가지고 있는 잔돈의 종류를 내림차순으로 리스트 money에 저장하기 -> 타로가 거슬러 받아야할 금액 (1000엔 - N엔)을 m에 저장하기 -> m엔을 리스트 money의 i번째 값으로 나눈 몫을 count에 누적해서 저장하기 -> m엔을 i번째 값으로 나눈 나머지를 다시 m에 저장하기 -> 위 과정을 money있는 요소들 들을 다 소진할 때까지 반복하기 -> 받을 잔돈에 포함된 잔돈의 개수 출력하기!

 

 

 

소스코드

N = int(input())

money = [500, 100, 50, 10, 5, 1]

m = 1000 - N
count = 0
for i in money:
    count += m // i
    m %= i

print(count)

 

728x90
반응형