[EPPER] 10회 4번

문제

 

---

풀이

 

그리디 알고리즘의 대표적인 문제이다. 해당 문제가 그리디 알고리즘으로 풀릴 수 있는 조건은 잔돈이 서로 배수관계여야 한다는 것이다. 예를 들어 잔돈이 10원, 7원, 1원이고 거스름돈이 14원이라면 7원 2개가 optimal choice지만, 그리디 알고리즘은 10원 1개, 1원 4개 총 5개를 지불해야 한다는 결과를 내놓는다.

 

다시 문제로 돌아가면, 해당 잔돈들을 coins 배열에 저장하고 가장 큰 잔돈부터 대입해보며 동전의 수를 더해나간다. 더이상 지불해야 할 거스름돈이 없는 경우에도 의미없이 반복문이 돌아가는 경우를 막고자 조건을 하나 더 추가했다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int coins[6] = { 500,100,50,10,5,1 };
	int C, M, remain, sum = 0;

	scanf("%d %d", &C, &M);
	remain = C - M; //거스름돈
	for (int i = 0; i < 6 && remain != 0; i++) {
		if (remain >= coins[i]) {
			sum += remain / coins[i];
			remain %= coins[i];
		}
	}
	printf("%d\n", sum);
}