백준 문제 링크

문제 정리

잔돈으로 500원, 100원, 50원, 10원, 5원, 1원이 있고 1000원을 냈을 때 받을 잔돈에 포함된 동전의 최소 개수를 구하는 프로그램을 작성하라.

해결 방법

• 그리디 방법으로 풀면 좋을 것 같다.
• 500 → 100 → 50 → 10 → 5 → 1 순으로 줄 수있는 거스름돈 중 가장 큰 금액부터 주는 것.

문제 풀이

money = 1000            # 최초 지불 금액
price = int(input())    # 상품의 가격
change = money - price  # 잔돈
count = 0               # 잔돈의 개수 (출력해야 하는 것)

# 동전의 종류들
coins = [500, 100, 50, 10, 5, 1]

# 동전의 종류들 별로 그리디 탐색
for coin in coins:
    count += change // coin   # 몫연산자로 개수를 더해준다. 
    change %= coin            # 나머지를 잔돈으로 바꿔준다.

print(count)