[AtCoder] [經典競程 90 題] 016 - Minimum Coins（★3）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_p
題目大意:
有三種幣值的硬幣 $A$, $B$, $C$ ，問要湊出 $N$ 元的話最少要多少硬幣，保證答案使用的總硬幣數不超過 $9999$

---

因為不超過 $9999$ ，所以直接枚舉 $A$ 用多少跟 $B$ 用多少就自然知道 $C$ 要用多少了。

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	lld n, a, b, c; cin >> n >> a >> b >> c;
	lld ans = n;
	for (lld i = 0; i <= 9999; ++i) {
		for (lld j = 0; j <= 9999; ++j) {
			if (a * i + b * j > n) break;
			lld lef = n - a * i - b * j;
			if (lef % c != 0) continue;
			ans = min(ans, i + j + lef / c);
		}
	}
	cout << ans << '\n';
	return 0;
}