[이코테] Chapter3-1 그리디 / 거스름돈

그리디(Greedy) : 탐욕스러운

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것을 고르고, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘

 

문제 요약

500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야 하는 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

나의 코드 및 설명 (성공)

• n : 거슬러 줘야 할 돈
• coin_list : 동전 종류 리스트
• coin : 동전(각 리스트 요소로 접근)
• count : 동전의 개수

n = int(input()) #440원 #1260

coin_list = [500,100,50,10]
count = 0
for coin in coin_list:
    if n >= coin:
        count += n // coin # coin=500, count=2 / coin=100, count=4 / 
                                  # coin=50, count=5 / coin=10, count=6
        n %= coin
    else:
        continue

print(count)

피드백

그리드 알고리즘 문제에 맞게 풀이하였다.

주의할 점은 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니란 것이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야한다. 예를 들어, 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원인 경우를 생각해보자. 이 경우엔 그리디 알고리즘으로는 4개의 동전(500원, 100원, 100원, 100원)을 거슬러 줘야 한다고 나오는데, 최적의 해는 2개의 동전(400원, 400원)을 거슬러 주는 것이다.

따라서, 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.