C++ 11047 동전0 (그리디알고리즘)

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

using namespace std;

int main() {

	int n, k;
	cin >> n >> k;

	vector<int>coin(n);
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	sort(coin.begin(), coin.end(), greater<int>());

	for (int i = 0; i < n; i++) {
		while (k - coin[i] >= 0) {
			cnt++;
			k -= coin[i];
		}
	}
	cout << cnt << '\n';
}

입력되는 숫자를 역순으로 정렬하고 입력된 k 값인 4,200원보다 작은 가장 큰 수(1000)부터 뺄셈을 진행하고 카운트를 늘림. 남는 200원도 동일하게 100원으로 빼주게 된다.

몇 개가 필요한지는 cnt로 확인 가능. 

 

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=namjs1540&logNo=221578707970 

백준 11047 동전 0 풀이 C++