硬貨の枚数1 [yukicoder No.634]

https://yukicoder.me/problems/no/634

解法

https://yukicoder.me/submissions/230870

解法はエスパーとフルフィードバック証明で作った。
DPでの解法が思いつくが、これは遷移数が多すぎてTLE
最大の数から貪欲で作るという方針もあるが、これはWAだった
こうなってくるとレベルも★2.5なので、特殊な何かに気付く必要があるっぽい。
今回の問題はゴールドバッハ予想に似ている。
最高3つの和で表現できそうな感じがある（サンプル見た感じ）。
1つで表現できる、2つで表現できるは比較的簡単に検証できるので、そこからも最高3つな感じがある。
　
まず硬貨を全て列挙しておく。
ここから1つずつ見ていき、硬貨に含まれるなら答え「1」
1つで表現できないなら、硬貨の1つを全探索してもう片方をlower_boundで存在するか確かめてみよう。
あるなら答え「2」
そうでないなら「3」

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<int> v;
    rep(k, 1, 20101) v.push_back(k * (k + 1) / 2);
    
    auto ite = lower_bound(all(v), N);
    if (ite != v.end() and *ite == N) {
        printf("1\n");
        return;
    }

    fore(i, v) if(i < N) {
        int d = N - i;
        auto ite = lower_bound(all(v), d);
        if (ite != v.end() and *ite == d) {
            printf("2\n");
            return;
        }
    }

    printf("3\n");
}