016.md

016 - Minimum Coins (★3)

解答

#include <iostream>
#include <algorithm> // std::min()

int main()
{
	// N 円支払う
	int N;
	std::cin >> N;

	// A 円硬貨, B 円硬貨, C 円硬貨
	int A, B, C;
	std::cin >> A >> B >> C;

	// 最小枚数
	int minCount = 10000;

	for (int aCount = 0; aCount <= 9999; ++aCount) // aCount: A 円硬貨の枚数
	{
		// A 円硬貨による合計金額
		const int a = (aCount * A);

		// 超えてたら打ち切る
		if (N < a)
		{
			break;
		}

		for (int bCount = 0; bCount <= (9999 - aCount); ++bCount) // bCount: B 円硬貨の枚数
		{
			// B 円硬貨による合計金額
			const int b = (bCount * B);

			// 超えてたら打ち切る
			if (N < (a + b))
			{
				break;
			}

			// もし残りの必要な金額を C 円硬貨で払いきれたら
			if ((N - (a + b)) % C == 0)
			{
				// C 円硬貨の枚数
				const int cCount = ((N - (a + b)) / C);

				// 合計枚数
				const int count = (aCount + bCount + cCount);

				// 最小枚数を更新
				minCount = std::min(minCount, count);
			}
		}
	}

	// 解答を出力
	std::cout << minCount << '\n';
}