Submission #2246019

---

Source Code Expand

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

const int INF = 1e8;
int dp[333];
int n;
int ng[5];

// xに遷移できるかを判定
bool invalid(int x) {
   if (x < 0) return true;
   for (int i = 0; i < 3; i++) {
      if (x == ng[i]) return true;
   }
   return false;
}

int main() {
   cin >> n;
   for (int i = 0; i < 3; i++) {
      cin >> ng[i];
      // NG候補の数がNなら初期状態でアウト
      if (n == ng[i]) {
         puts("NO");
         return 0;
      }
   }

   for (int i = 0; i < 310; i++) dp[i] = INF; // DPテーブルを大きい値で初期化
   dp[n] = 0; // スタートの手数は0
   for (int i = n; i >= 0; i--) { // iからの遷移
      for (int j = 1; j <= 3; j++) { // iからi-jへの遷移の最小手数を考える
         if (invalid(i-j)) continue;
         dp[i-j] = min(dp[i-j], dp[i]+1);
      }
   }

   if (dp[0] <= 100) {
      puts("YES");
   } else {
      puts("NO");
   }

   return 0;
}

Submission Info

Judge Result