• 그리디 알고리즘(탐욕법)은 현재 상황에서 가장 좋은 것만 고르는 방법 (단순히 매 상황에서 가장 좋아보이는 방법)
• 정당성을 분석하는 것이 중요하다.
• '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' (정렬, 최단 경로 등의 유형은 미리 사용 방법을 정확이 알고 있어야 함)

숫자 카드 게임 - 실전 문제

1이 될 때까지 - 실전 문제

<문제> 거스름 돈

• 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. (단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

[정당성 분석]

→ 가장 큰 화폐단위부터 거슬러 줘야 하는 것이 최적 !

• 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없다.

array = [500, 100, 50, 10]

r = int(input())
count = 0

for coin in array:
    nofr = r // coin
    print('{}won: '.format(coin), nofr)
    count += nofr
    r %= coin

print('총 거슬러 줘야 할 동전의 개수는 :', count)