[Python] 백준 5585번_거스름돈

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

5585번: 거스름돈

 

• JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 줌
• 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수 구하기

• 입력
  • 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있음
• 출력
  • 제출할 출력 파일은 1행으로만 되어 있고, 잔돈에 포함된 매수를 출력
• 시간 제한: 1초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

(예제 입력 1) 
380 -> 4

(예제 입력 2)
1 -> 15
"""

 

 

## 의사코드 ##

# 거스름돈 개수가 가장 적게 -> 금액이 가장 큰 잔돈부터 차감

# 잔돈 리스트(coins) = [500, 100, 50, 10, 5, 1]
# 잔돈 리스트를 내림차순 정렬 -> 가장 큰 값부터

# 거스름돈 = 1000 - 타로가 지불할 돈(입력)
# 잔돈 개수 = 0
# for c in coins:
#   n = 거스름돈 // c # 동전이 필요한 개수
#   거스름돈 -= c * n 
#   잔돈 개수 += n 

# print(잔돈 개수)

 

 

 

통과한 코드

 

price = int(input()) # 타로가 지불할 돈
coins = [500, 100, 50, 10, 5, 1] # 잔돈 리스트

# 거스름돈 계산
change = 1000 - price
# 잔돈 리스트 내림차순 정렬
coins.sort(reverse=True)

change_n = 0 # 잔돈 개수 
for c in coins:
    n = change // c # 필요한 동전의 개수
    change_n += n # 잔돈 개수 + n
    change -= c * n # 남은 거스름돈 계산 

print(change_n)

 

-> 다시 보니 잔돈 리스트가 이미 내림차순 정렬되어 있으므로 굳이 다시 정렬하지 않아도 됨

 

 

 

다른 풀이

 

change = 1000 - int(input())
count = 0

for i in [500, 100, 50, 10, 5, 1]:
    count += change // i
    change %= i 

print(count)

-> 잔돈을 input() 받아온 값으로 바로 계산하고, 남은 거스름돈을 동전으로 나눈 나머지로 계산

 

 

• 과정 확인

# 1 -> 15

"""
원래 change: 999 

i: 500
필요한 동전의 개수: 1
전체 잔돈의 개수(count): 1
남은 change: 499 

i: 100
필요한 동전의 개수: 4
전체 잔돈의 개수(count): 5
남은 change: 99 

i: 50
필요한 동전의 개수: 1
전체 잔돈의 개수(count): 6
남은 change: 49 

i: 10
필요한 동전의 개수: 4
전체 잔돈의 개수(count): 10
남은 change: 9 

i: 5
필요한 동전의 개수: 1
전체 잔돈의 개수(count): 11
남은 change: 4 

i: 1
필요한 동전의 개수: 4
전체 잔돈의 개수(count): 15
남은 change: 0 
"""