[백준 9658] 돌 게임 4 (C#, C++) - soo:bak

문제 링크

9658번 - 돌 게임 4

설명

두 사람이 1개, 3개 또는 4개의 돌을 번갈아 가져갈 수 있을 때, 누가 이기는지 구하는 문제입니다.

관련 문제: [백준 9655] 돌 게임 3 (C#, C++) - soo:bak

위 문제와 같은 방식으로 진행되지만, 마지막에 돌을 가져가는 사람이 이기는 것이 아니라 진다는 조건만 다릅니다.

따라서, 점화식과 대상을 반대로 뒤집으면 됩니다.

관련 문제: [백준 9655] 돌 게임 (C#, C++) - soo:bak

관련 문제: [백준 9656] 돌 게임 2 (C#, C++) - soo:bak

관련 문제: [백준 9659] 돌 게임 5 (C#, C++) - soo:bak

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var dp = new bool[1001];
    dp[1] = true;
    dp[3] = true;

    for (int i = 4; i <= n; i++)
      dp[i] = !dp[i - 1] && !dp[i - 3] && !dp[i - 4];

    Console.WriteLine(dp[n] ? "CY" : "SK");
  }
}

C++

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  bool dp[1001] = {false, true, false, true};
  for (int i = 4; i <= n; i++)
    dp[i] = !dp[i - 1] && !dp[i - 3] && !dp[i - 4];

  cout << (dp[n] ? "CY\n" : "SK\n");
  return 0;
}