[그리디 알고리즘 Lv.02] 5585번 거스름돈 (Python)

 

1. 문제

    5585번 거스름돈 (https://www.acmicpc.net/problem/5585)

    

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

 

 

2. 문제 포인트

• 거스름돈 종류 (500엔, 100엔, 50엔, 10엔, 5엔, 1엔)
• 잔돈 개수의 최소값

 

반응형

 

3. 접근법

• 큰 금액 동전을 최대한 많이 사용하면 되는 문제
• 1엔짜리까지 있기에 단순하게 계산 가능
    (1엔짜리가 없을 경우 잔돈의 1의 자리가 5나 0으로 끝나지 않으면 계산 불가)

 

4. 결과 코드

import sys

a = int(sys.stdin.readline())

# 잔돈 금액 계산
chg = 1000 - a

# 동전 단위 리스트 (큰 동전부터 내림차순)
coin = [500, 100, 50, 10, 5, 1]

# 동전 개수
coin_cnt = 0

# coin에 들어있는 동전 단위별로 반복
for n in coin:
    
    # n값으로 나눠지면 계산
    if chg // n > 0:
        # 코인 개수 추가
        coin_cnt += chg // n
        # 현재 단위 제외 후나머지 잔액 계산
        chg -= n * (chg // n)

# 결과값 출력
print(coin_cnt)

# 5585번 거스름돈
# https://www.acmicpc.net/problem/5585