3-1. 당장 좋은 것만 선택하는 그리디

그리디 알고리즘이란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 따라서 최적의 해를 보장할 수 없을 때가 많다.

하지만 코딩테스트에서는 그리디로 얻은 해가 최적의 해가 되는 상황을 추론할 수 있어야 풀리도록 출제된다.

 

해결 아이디어

1. 최적의 해를 구하기 위해 가장 큰 단위부터 거슬러 준다.

2. 그 이유는 무엇일까? 큰 단위가 항상 작은 단위의 배수이기 때문이다. 

3. 800원을 거슬러주어야 할 때 화폐 단위가 500, 400, 100이라면 500은 400의 배수가 아니기 때문에 최적의 해를 구할 수 없다.

 

예제 3-1. 거스름 돈

# 나의 풀이
money = int(input())  # 거스름돈 1260
count = 0
if money//500 > 0:
    count += (money//500)
    money -= 500*(money//500)
    # money를 나누고, 남은 나머지를 money에 다시 넣어준다.
    # money %= 500를 하면 260이 남음
if money//100 > 0:
    count += (money//100)
    money -= 100*(money//100)
if money//50 > 0:
    count += (money//50)
    money -= 50*(money//50)
if money//10 > 0:
    count += (money//10)
    money -= 10*(money//10)
print(count)

# 해설
money = 1260
coin = [500, 100, 50, 10]
count = 0
for i in coin:
    count += money//i
    money %= i
print(count)