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

• 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
• 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
• 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

예제 3 - 1. 거스름돈 (p. 87)

<내 풀이>

N = int(input())
coin = 0
i = 1
while N // (i*500) > 0:
    coin += 1
    i += 1
    while N // (i*100) > 0:
        coin += 1
        i += 1
        while N // (i*50) > 0:
            coin += 1
            i += 1
            while N // (i*10) > 0:
                coin += 1
                i += 1
                if N == 0:
                    break
print(coin)

1260
-> 126
이게 이렇게 복잡해야하는건가...??

<정답>

N = int(input())
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
	count += n // coin
    n %= coin
print(count)