백준 11047 - 동전 0

동전의 종류, 금액이 주어졌을 때 금액을 만들 수 있는 최소한의 동전의 개수를 구하는 문제입니다.

가장 큰 금액이 많이 사용될 수록 동전을 더 적게 사용하니 큰 수부터 차례로 계산하면 됩니다.

#include <iostream>
#include <vector>

int main()
{
	int N, K;
	std::vector<int> coinValues;

	std::cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		int value;
		std::cin >> value;

		coinValues.push_back(value);
	}

	int cnt = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		cnt += K / coinValues[i];
		K -= coinValues[i] * (K / coinValues[i]);
	}

	std::cout << cnt;

	return 0;
}