그리디

: 현재 상황에서 지금 당장 좋은 것만 고르기 (가장 큰 순서대로 or 가장 작은 순서대로)

이런 경우는 그리디 ❌

---

예제

💰 거스름돈

📌 거스름돈이 배수 관계이기 때문에 최적의 해 보장 -> 그리디 사용

문제

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 거슬러 줘야할 돈 N은 항상 10의 배수이다.

입력

거슬러 줘야할 금액

출력

손님에게 거슬러 줄 때 필요한 동전의 개수

⌨️ 코드

n = 1260
cnt = 0

a = [500,100,50,0]

for coin in a:
	cnt += n//coin
    n %= coin
    
print(cnt)

---

관련문제: 백준 5585번 거스름돈

백준 5585 바로가기

⌨️ 코드

n = int(input())
count = 0
money = 1000-n
array = [500, 100, 50, 10, 5, 1]

for coin in array:
    count += money // coin
    money %= coin
    
print(count)

---

관련문제: 백준 14916번 거스름돈

백준 14916 바로가기

⌨️ 코드

n = int(input())

cnt = 0

while True:
    if n%5 == 0:
        cnt += n//5
        break
    
    else:
        n-=2
        cnt += 1

if n < 0: print(-1)
else: print(cnt)