問題
A円、B円、C円と硬貨が3種類ある。
それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。
解法
そのまま全探索すると になり、TLEする。
そのためループを3重から2重へと減らす必要がある。
xとyの値が決まれば で定まるのでへ落とせる。
所感
制約にもよるが、3重ループはTLEになる場合が多い。
ちょっとした工夫で大幅に計算量が減らせる事もあるので、いろんな視点で考えるようにしたい。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { ll n, a, b, c; cin >> n; cin >> a >> b >> c; ll ans = INFL; for (ll i = 0; i <= 9999; i++) { for (ll j = 0; j <= 9999 - i; j++) { ll tmp = n - (a * i) - (b * j); if (tmp < 0) continue; if (tmp % c == 0) // ここで余りを求めて判定することで、ループを削減する。 { ll cnt = i + j + tmp / c; chmin(ans, cnt); } } } cout << ans << endl; return 0; }