100 to 105 [Sumitomo Mitsui Trust Bank Programming Contest 2019 C]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c

前提知識

• yes/no系動的計画法

解説

https://atcoder.jp/contests/sumitrust2019/submissions/8776665

品物は10⁶個あるので、足りなくなることはない。
DPしよう。yes/noのDPをする。
dp[x] := ちょうどx円となる買い物ができるか
遷移は6通りなので、できる。

int X;
bool dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X;
    dp[0] = true;
    rep(x, 0, X) if(dp[x]) rep(d, 0, 6) dp[x + d + 100] = true;

    if (dp[X]) cout << "1" << endl;
    else cout << "0" << endl;
}