백준 #11047. 동전 0

그리디 알고리즘을 이용해 풀었다.

K원을 만드는 데 필요한 동전들은 K원보다 작은 동전들이다.

coin 배열을 n-1번째 인덱스부터 0번째 인덱스로 거꾸로 받고, 0번째 인덱스부터 차례대로 K원을 만족시킬 수 있는지 알아본다.

만약 i번째 인덱스가 K원보다 크다면, 다음 인덱스를 탐색한다. 만족하는 인덱스의 숫자(동전 숫자)는 K원보다 작을 때까지 더해준다.

 

가령, K원을 4200원이라고 했을 때, 50000원, 10000원, 5000원으로는 절대 4200원을 만들 수 없다. 그러니 스킵하고, 1000원을 만나면 그걸 4만큼 반복해서 더해준다. 그럼 4000원이 된다.

그 다음 500원을 더하면 4500원이 되므로, 500원을 낄 수 없다. 얘도 스킵!

그 다음은 100원이다. 4100원 <= 4200원, 4200원 <= 4200원이므로 100원을 2번 반복해 더해준다.

 

그럼 1000원짜리 4장과 100원짜리 2개, 즉 총 6개가 바로 4200원을 만드는 최소 동전 개수이다.

 

 

다음은 소스코드이다.

 

#include <iostream>
using namespace std;

int main() {

	int n, result, sum = 0, count = 0; //sum: sum of coins, count: coin count
	int coin[10];
	cin >> n >> result;

	for (int i = n - 1; i >= 0; i--) { //get coin array (desc order)
		cin >> coin[i];
	}

	for (int i = 0; i < n; i++) {
		if (sum == coin[i]) break; 
		if (sum + coin[i] > result) continue;

		while (sum + coin[i] <= result) {
			sum += coin[i];
			count++;
		}

	}

	cout << count;

	return 0;
}