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

문제 링크

9657번 - 돌 게임 3

설명

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

돌의 개수 N이 주어지고, 상근이가 먼저 시작합니다.

돌은 한 번에 1개, 3개, 4개 중 원하는 개수만큼 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 승리하게 됩니다.

접근법

현재 돌의 개수에 따라 누가 이기게 되는지를 순차적으로 판단해야 하므로,

각 개수별 결과를 저장하면서 점진적으로 해결하는 방식이 적합합니다.

즉, 돌의 개수가 증가할 때마다 상근이가 이길 수 있는지 여부를 기록하며 계산을 이어갑니다.

이를 위해 남은 돌의 개수를 기준으로 한 bool 배열을 만들어,

해당 상황에서 상근이가 이길 수 있다면 참, 그렇지 않으면 거짓으로 설정합니다.

예를 들어 돌이 i개 남았을 때, 상근이는 1개, 3개, 4개를 가져갈 수 있습니다.

즉, 다음 상태는 각각 i - 1, i - 3, i - 4개의 돌이 남은 상태입니다.

이 중 하나라도 창영이가 이길 수 없는 상태로 만들 수 있다면,

현재 상황은 상근이에게 유리한 상태입니다.

반대로 세 경우 모두 창영이가 이기는 상황이라면, 상근이는 어떤 선택을 하더라도 패배하게 됩니다.

이 논리를 바탕으로 다음과 같은 조건이 도출됩니다:

• 현재 돌이 i개 남았을 때:
  • i - 1, i - 3, i - 4개의 상태가 모두 상근이가 이기는 상태라면,
    → 상근이가 아무리 가져가도 상대가 유리해짐 → 현재는 지는 상태
  • 이외의 경우 중 하나라도 상대에게 불리한 상태가 있다면,
    → 상근이가 그 쪽으로 넘김 → 현재는 이기는 상태

이를 바탕으로 다음과 같은 점화식을 유도할 수 있습니다:

dp[i] = !dp[i - 1] || !dp[i - 3] || !dp[i - 4];

이 방식으로 1부터 차례대로 돌의 개수에 따라 승패 여부를 채워가면,

마지막 상태에서 상근이의 승패 여부를 결정할 수 있습니다.

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

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

관련 문제: [백준 9656] 돌 게임 4 (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] ? "SK" : "CY");
  }
}

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] ? "SK\n" : "CY\n");
  return 0;
}