[C/C++] 나동빈 거스름돈, Greedy

문제

거슬러줘야 할 돈이 N원일 때, 거스름돈으로 사용할 동전 500원, 100원, 50원 그리고 10원을 조합한 동전의 최소 개수를 구하라.  단, N은 항상 10의 배수이다.

코드

#include<stdio.h>
#include <iostream>

using namespace std;
int coin[4] = { 500,100,50,10 };
int main() {
	int N, sum = 0;
	cin >> N;
	for (int i = 0; i < 4; i++) {
		sum += N / coin[i];
		N %= coin[i];
	}
	cout << sum;
}

풀이

1. 동전의 최소 개수를 구해야 하므로, 단위가 가장 큰 동전(500원)부터 내림차순으로 배열 coin 에 저장한다.

2. for문을 통해 N을 coin[i]로 나눈 몫만큼 sum에 더한 후

3. N을 coin[i]로 나눈 나머지 값으로 초기화한다.