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

 

이번 문제는 가치의 합이 주어졌을 때 그 합을 이루는 최소한의 동전 개수를 구하는 문제이다.

따라서, 그리디 알고리즘으로 풀 수 있다.

 

간단하게, 그리디 알고리즘은 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식이다.

알고리즘 풀이법은 1단계 선택절차를 통해 현 상태에서 최적의 선택을 하도록 한다. 2단계 적절성 검사를 통해 문제의 조건을 만족하는지 확인한 후 답을 도출한다.

 

최소한의 동전을 사용하려면, 최대한 가장 화폐단위가 큰 동전을 사용하면 된다.

가치의 합 K를 단위가 가장 큰 동전부터 나누어 개수를 세어주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;

	vector <int>arr(n+1);

	int value;
	for (int i = 0; i < n; i++) {
		cin >> value;
		arr[i] = value;
	}

	// 1. 선택 절차
	// sort(arr.begin(), arr.end());

	// 2. 적절성 검사
	int sum = 0;
	for (int i = n - 1; i >= 0 ; i--) {
		sum += k / arr[i];
		k = k % arr[i];
	}

	// 3. 해답 검사
	cout << sum;
}