[Problem Solving] 거스름돈

그리디, 탐욕법

그리디 알고리즘 : 단순하지만 강력한 문제 해결 방법. 다른 말로 탐욕법이라고도 함. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘.

 

탐욕적? '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하되, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다.

 

문제 : 거스름돈

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재. 거슬러 줘야 할 돈이 N원일 때 최소 동전의 개수? (단, N은 항상 10의 배수)

n = int(input())  # 거스름돈 n을 정수로 입력받는다.
count = 0  # 최소 동전의 개수

coin_types = [500, 100, 50, 10]  # 큰 단위의 화폐부터 차례대로 확인

coin_counts = []  # 각 단위의 화폐 수 저장

for coin in coin_types:
    count += (n // coin)  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    coin_counts.append(n // coin)  # 동전 개수 저장
    n %= coin  #  해당 화폐로 거슬러 주고 남은 거스름 돈

print(f"최소 동전 개수 : {count}개")

idx = 0

# 각 화폐 동전 개수 출력
for coin in coin_types:
    if idx == 4:
        break
    print(f"{coin}원 동전 개수 : {coin_counts[idx]}개")
    idx += 1

#  출력 예시
#  거스름돈 n : 5120
#  최소 동전 개수 : 13개
#  500원 동전 개수 : 10개
#  100원 동전 개수 : 1개
#  50원 동전 개수 : 0개
#  10원 동전 개수 : 2개