[이코테] 3. 그리디 알고리즘 - 거스름 돈

그리디 알고리즘 - 거스름 돈 문제 설명 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님이게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 문제 해결 아이디어 " 가장 큰 화폐 단위 부터 " 돈을 거슬러 주면 됨. (최적의 해) N원 거슬러 줘야 할 때 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줌. 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줌. 정당성 분석 가장 큰 화폐 단위부터 거슬러 주는 것이 최적의 해가 되는 이유는? : 가지고 있는 동전 중에서 큰 단위가 항상 작은..