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

문제 링크

9660번 - 돌 게임 6

설명

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

상근이가 먼저 시작하며, 마지막 돌을 가져가는 사람이 승리합니다.

N이 최대 10¹²로 매우 크므로 일반적인 동적 프로그래밍 방식으로는 해결할 수 없습니다.

접근법

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

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

돌이 i개 남았을 때, 1개, 3개, 4개를 가져갈 수 있으므로 상대에게 (i-1)개, (i-3)개, (i-4)개 중 하나를 남기게 됩니다.

이 세 가지 중 하나라도 상대가 지는 상태라면 현재 상태는 이기는 상태이고, 세 가지 모두 상대가 이기는 상태라면 현재 상태는 지는 상태입니다.

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

• 1개: 1개 가져가면 승리 → 이기는 상태 (SK)
• 2개: 1개 가져가면 상대가 1개(이김), 다른 선택 불가 → 지는 상태 (CY)
• 3개: 3개 가져가면 승리 → 이기는 상태 (SK)
• 4개: 4개 가져가면 승리 → 이기는 상태 (SK)
• 5개: 1개 가져가면 상대가 4개(이김), 3개 가져가면 상대가 2개(짐) → 이기는 상태 (SK)
• 6개: 1개→5개(이김), 3개→3개(이김), 4개→2개(짐) → 이기는 상태 (SK)
• 7개: 1개→6개(이김), 3개→4개(이김), 4개→3개(이김) → 지는 상태 (CY)
• 8개: 1개→7개(짐) → 이기는 상태 (SK)
• 9개: 1개→8개(이김), 3개→6개(이김), 4개→5개(이김) → 지는 상태 (CY)

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

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

관련 문제: [백준 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 % 7;
      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 % 7;
  if (mod == 0 || mod == 2) cout << "CY\n";
  else cout << "SK\n";
  return 0;
}