[Algorithm] 탐욕법(Greedy)

Greedy

-Greedy : 탐욕스러운, 욕심 많은

-미래를 생각하지 않고 현재 상황에서 가장 최선의 선택을 하는 알고리즘

-'가장 큰 순서대로', '가장 작은 순서대로'와 같은 키워드 제시

-정렬 알고리즘과 함께 나오는 경우 많음

 

거스름돈

카운터에는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러줘야 하는 동전의 최소 갯수를 구하여라. 단, 거슬러 줘야 하는 돈 N은 항상 10의 배수이다.

n = int(input())
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
    count += n // coin
    n = n % coin

print(count)

문제풀이

-문제 해결 포인트 : 가장 큰 화폐 단위부터 거슬러 주기

-시간 복잡도 : O(K) (K는 화폐의 종류)

-정당성 : 큰 화폐 단위가 항상 작은 화폐 단위의 배수이므로 작은 화폐 단위의 동전들로 다른 해가 나올 수 없음

    예) 500원, 400원, 100원짜리 동전이 존재. 거슬러 줘야 하는 돈은 800원

            ⅰ. Greedy : 4개 (500원-1개, 100원-3개)

            ⅱ. 실제 : 2개 (400원-2개)

            (큰 화폐 단위가 작은 화폐 단위의 배수가 아닌 경우, 다이나믹 프로그래밍으로 풀이)