CPSCO2019 Session1-C: Coins

問題概要

問題リンク

1, 10, 100, ..., 10⁹, 5, 50, 500, ..., 5 * 10⁹円硬貨がある
スーパーでN種類の果物が1つずつ、それぞれA₀,A₁, ..., A_n-1円で売られている

N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を求めよ
ただし、硬貨の数は限りなく多いとする

考察

たくさんの硬貨…？ Strange Bankか？ と思ったが、大きい硬貨から順番に払っていけば最小の硬貨枚数となるので別問題であると分かった(Strange Bankだと13円の場合、12円以下で大きい値の硬貨から貪欲に削っていくと、9円と1円と1円と1 円の硬貨の４枚となる。しかし6円と6円と1円の３枚が最小の硬貨枚数となる)

硬貨の最小枚数を考える前に、K個の果物を選ぶ方法を考える
_nC_kを列挙してやれば良いのは分かるが実装方法が分からない…
例えば N = 5, K = 3の場合，{A[0], A[1], A[2]}, {A[0], A[1], A[3]}, {A[0], A[1], A[4]}, ...と順々に列挙する必要がある

順々…？列挙…？ …深さ優先探索！！！！！！！！！
AOJ-整数の和が頭に浮かんだ

↑こんなイメージで探索していき、遷移数がKになったときの合計金額を、持っている合計金額以下の硬貨で徐々に減らしていき、硬貨枚数をカウントしてすべての遷移後の硬貨枚数の最小値が答え

うまく説明できなくてアレですが、いけるとこまでいくぜ〜感で探索するイメージです

コード

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

long long n, k, ans = 1e9;
long long A[35];

vector<long long> Coin;

void dfs(long long now, long long cnt, long long total){
    if(cnt == k){
        long long cc = 0; // coin_count
        for(long long i = 0; i < Coin.size(); i++){
            if(Coin[i] > total) continue;
            while(total - Coin[i] >= 0){
                cc++;
                total -= Coin[i];
            }
        }
        ans = min(ans, cc);
    }else{
        for(long long i = 0; i < n; i++){
            if(now + 1 + i < n){
                dfs(now + 1 + i, cnt + 1, total + A[now + i + 1]);
            }
        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for(long long i = 0; i < n; i++){
        cin >> A[i];
    }

    for(long long i = 0; i < 9; i++){
        Coin.push_back((long long)pow(10, i));
        Coin.push_back((long long)(5 * pow(10, i)));
    }

    sort(Coin.rbegin(), Coin.rend());

    for(long long i = 0; i < n; i++){
        dfs(i, 1, A[i]);
    }

    cout << ans << endl;

    return 0;
}

atcoder.jp

宣伝

cp-categorizeというサイトに自分で解いた競プロの問題を勝手にジャンル分けしています。深さ優先探索の問題は地道に解いているのでそこそこの問題量があります。ぜひサイトを覗いてみてください！