[C++] 백준 11047번 동전 0

 

N개의 동전 종류가 있을 때 동전들을 합하여서 K라는 값을 최소한의 동전을 이용해서 만드는 문제입니다.

 

입력되는 수들이 오름차순으로 주어지기 때문에 큰값들부터 비교를 해서 

찾는 값 K 보다 작으면서 가장 큰 값 v[i]를 value가  K를 넘지 않을때 까지 더합니다. 이와 동시에 카운트를 해줍니다.

이와 같은 과정을 반복하여 총 몇번의 카운트를 통해서 값을 찾을 수 있는지 확인할 수 있습니다.

 

K보다 작은 가장 큰값들을 더해서 최소의 횟수를 찾았습니다.

이와 같은 알고리즘을 그리디 알고리즘이라고 합니다.

 

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char * argv[])
{
	int N;
	int K;
	int x;
	int value = 0;
	int count = 0;
	vector<int> v;

	cin >> N;
	cin >> K;

	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}
	
	for (int i = N-1; 0 <= i; i--) {
		while(v[i] <= K && value + v[i] <= K) {
			value += v[i];
			count++;
		}
	}

	cout << count << endl;

	return 0;
}