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

문제 링크

9661번 - 돌 게임 7

설명

두 사람이 4의 거듭제곱 개수(1개, 4개, 16개, 64개, …)의 돌을 번갈아 가져가는 게임에서, N (1 ≤ N ≤ 10¹²)개의 돌이 주어질 때, 두 사람이 최적의 전략으로 플레이한다면 누가 이기는지 판별하는 문제입니다.

상근이가 먼저 시작하며, 가져갈 돌이 없어 움직일 수 없는 사람이 패배합니다.

N이 최대 10¹²로 매우 크므로 모든 경우를 직접 계산할 수 없습니다.

접근법

게임 이론에서 특정 상태는 ‘이기는 상태’와 ‘지는 상태’로 구분됩니다.

현재 차례인 사람이 어떤 선택을 해도 상대를 이기는 상태로 보낼 수밖에 없다면 현재 상태는 지는 상태이고, 반대로 상대를 지는 상태로 보낼 수 있는 선택지가 하나라도 있다면 현재 상태는 이기는 상태입니다.

돌이 i개 남았을 때, 4⁰=1개, 4¹=4개, 4²=16개, 4³=64개, … 중에서 i 이하인 값을 가져갈 수 있습니다.

가져간 후 상대에게 남기는 돌의 개수 중 하나라도 상대가 지는 상태라면 현재 상태는 이기는 상태이고, 모두 상대가 이기는 상태라면 현재 상태는 지는 상태입니다.

작은 경우부터 차례대로 계산해보면:

• 0개: 가져갈 돌이 없음 → 지는 상태 (상대가 이미 승리)
• 1개: 1개 가져가면 상대가 0개(짐) → 이기는 상태 (SK)
• 2개: 1개 가져가면 상대가 1개(이김), 4개는 불가 → 지는 상태 (CY)
• 3개: 1개 가져가면 상대가 2개(짐) → 이기는 상태 (SK)
• 4개: 4개 가져가면 상대가 0개(짐) → 이기는 상태 (SK)
• 5개: 1개→4개(이김), 4개→1개(이김) → 지는 상태 (CY)
• 6개: 1개→5개(짐) → 이기는 상태 (SK)
• 7개: 1개→6개(이김), 4개→3개(이김) → 지는 상태 (CY)
• 8개: 1개→7개(짐) → 이기는 상태 (SK)
• 9개: 1개→8개(이김), 4개→5개(짐) → 이기는 상태 (SK)
• 10개: 1개→9개(이김), 4개→6개(이김) → 지는 상태 (CY)

이 패턴을 계속 이어가면 5개 단위로 반복되며, N을 5로 나눈 나머지가 0 또는 2일 때만 지는 상태(CY 승리), 나머지 경우는 모두 이기는 상태(SK 승리)입니다.

따라서 N이 매우 크더라도 N을 5로 나눈 나머지만으로 즉시 승패를 판정할 수 있습니다.

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

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

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

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

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

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      ulong n = ulong.Parse(Console.ReadLine()!);
      ulong mod = n % 5;
      if (mod == 0 || mod == 2) Console.WriteLine("CY");
      else Console.WriteLine("SK");
    }
  }
}

C++

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

typedef unsigned long long ull;

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

  ull n; cin >> n;
  ull mod = n % 5;
  if (mod == 0 || mod == 2) cout << "CY\n";
  else cout << "SK\n";
  return 0;
}