문제 출처

1. 문제설명

  • N 종류의 동전이 주어진다.
    • 동전의 가치는 오름차순으로 주어진다.
  • 동전을 최소로 활용해서 K를 만들고자 한다.
  • 사용되는 동전의 최소 개수를 구하라.



2. 알고리즘 설계

  • 현재 동전의 가치가 K보다 작거나 같다면,
    • K로 나누고, 현재 동전의 가치는 K로 나눈 나머지로 저장한다.
    • 몫을 카운팅한 게 정답이 된다.



3. 전체 코드

#include<bits/stdc++.h>
using namespace std;

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

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

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

	for (int i = n - 1; i >= 0; i--) {
		if (v[i] <= k) {
			ans += k / v[i];
			k = k % v[i];
		}
	}

	cout << ans;
	return 0;
}