https://atcoder.jp/contests/cpsco2019-s1/submissions/15470682
- Kが小さいのでK種類の商品を全探索する
- 大きい硬貨から貪欲に支払いを構成する
Nが32なので全探索はできないが、Kが最大6なので
個の全探索は出来そうという気持ちになる。小さい硬貨で支払うと使う枚数が増えてしまうため、大きい硬貨から貪欲に支払金額を構成する。K個の
合計を全列挙するために、蟻本p144に載っているアルゴリズムを使って
のビットテーブルを作る。全体計算量は
