[AtCoder] 三井住友信託銀行プログラミングコンテスト2019 C – 100 to 105

2019年12月2日

問題

方針

動的計画法を行い、\( X \) を作れるかどうかを調べます。\( i \) 円が作れるとき、\( i + 100 \) 円も作れるというような方針で実装します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int X;
    cin >> X;
    int dp[X + 1000]{};
    dp[0] = 1;
    int a[6] = {100, 101, 102, 103, 104, 105};
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < X; j++) {
            if (dp[j] == 1) {
                dp[j + a[i]] = 1;
            }
        }
    }
    cout << dp[X] << "\n";
    return 0;
}