🍔 그리디 알고리즘

🍔 그리디 알고리즘

• 그리디 알고리즘은 탐욕적인 알고리즘이라는 뜻으로 “현재 상황에서 지금 당장 좋은것만 선택하는것”을 의미한다.
• 그리디 알고리즘은 문제풀이가 정당한지 검토할 수 있어야 답을 도출할 수 있다.

🍔 거스름돈 예제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500, 100, 50, 10원짜리 동전이 무한히 존재한다고 가정한다., 손님에게 거슬러 줘야 할 돈이 N원일때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

n = int(input())
cnt = 0

coin = [500, 100, 50, 10]

for i in coin:
  cnt += n//i
  n = n%i

print(cnt)