ryo’s blog

日々学んだことをまとめています.

競プロ典型90問 016(★3) 全探索

016 - Minimum Coins(★3)

問題

A円、B円、C円と硬貨が3種類ある。

それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。

解法

そのまま全探索すると  O ( N ^ 3 ) になり、TLEする。

そのためループを3重から2重へと減らす必要がある。

xとyの値が決まれば z=(N-Ax-By)/C で定まるので O ( N ^ 2 ) へ落とせる。

所感

制約にもよるが、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;
}