그리디 알고리즘 개념 요약

1. 단순하지만 강력한 문제 해결 방법.

2. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형.

3. 다익스트라 알고리즘 또한 그리디 알고리즘.

4. 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력.

5. 문제를 만났을 때 단순히 현재 상황에 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

6. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은

   기준을 알게 모르게 제시해준다.

7. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는

   자주 정렬 알고리즘과 짝을 이뤄 출제된다.

8. 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토.

9. 문제 유형을 바로 파악하기 어려울 때, 그리디 알고리즘을 의심하고, 최소한의 아이디어를 떠올려보자.

# 3-1.거스름돈
n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin // 나머지
    
print(count)