[백준] 11047 c++ 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

입력받은 동전값들을 내림차순으로 정렬해준후 빼기 시작했다.

그리디하면 제일 먼저 떠오르는 동전문제.. 오랜만에 하니 기억이 가물가물해서 고생했다.

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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k, ans = 0;
	cin >> n >> k;

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

	sort(arr.begin(), arr.end(), greater<>());

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