[BaekJoon] 9661 돌 게임 7 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/9661

2.  문제

요약

• 돌 게임은 두 명이서 즐기는 게임인데, 처음에는 탁자 위에 돌 N개가 있습니다.
• 상근이와 창영이는 턴을 번갈아가며 돌을 가져가고, 돌은 $4^x$개만큼 가져갈 수 있습니다.
• $4^x$개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 됩니다.
• 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 문제입니다. 게임은 상근이가 먼저 시작합니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000,000,000보다 작거나 같은 N이 주어집니다.
• 출력: 첫 번째 줄에 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long N;

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Long.parseLong(br.readLine());
    }

    static void solution() {
        System.out.println((N % 5 == 0 || N % 5 == 2) ? "CY" : "SK");
    }

    static double baseLog(long num, long base) {
        int exponent = (int)Math.floor(Math.log10(num) / Math.log10(base));
        return Math.pow(base, exponent);
    }

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }
}

4.  접근

• $4^x$개로 돌을 번갈아가며 가져갔을 때, N이 1일 때부터 20까지 상근이가 이길 수 있는 상황이 존재하는지에 대한 규칙을 찾기 위해 아래와 같은 코드로 확인합니다.

  • 창영이가 한 번이라도 지는 상황이 존재한다는 뜻은 그 때는 상근이가 이길 수 있다는 뜻이므로 창영이가 한 번이라도 지는 상황이 존재한다면 상근이가 이겼는지에 대한 여부를 나타내는 SKWin 배열의 값을 true로 합니다.

  boolean[] SKWin = new boolean[20];
  
  for(int rock = 1; rock <= 20; rock++) {
      int x = 0;
  
      while(rock - Math.pow(4, x) >= 0) {
          // 창영이가 지는 상황이 있다면
          if(!SKWin[rock - (int)Math.pow(4, x)]) {
              SKWin[rock] = true; // 상근이가 이기는 상황이 존재할 수 있다
              break;
          }
  
          x++;
      }
  }

  • N이 0일 때는 애초에 가져갈 돌이 없기 때문에 상근이가 돌을 못 가져가므로 false가 됩니다.
  • N이 1일 때는 상근이가 돌 1개를 가져가면 창영이가 돌을 가져가지 못하므로 지게 되기 때문에 true가 됩니다.
  • 이와 같은 방식으로 진행하다보면 false true false true true가 반복적으로 나타납니다.
  • 이 규칙을 이용하여 정답을 구합니다.

• 탁자 위에 놓인 돌 개수를 입력받아 N이라는 변수에 저장합니다.
• false true false true true의 규칙이 반복되므로 5로 나눈 나머지가 0이거나 2라면 창영이가 이기게 되고 나머지가 1, 3, 4라면 상근이가 이기게 됩니다.
• 그러므로 N을 5로 나눈 나머지가 0이나 2라면 CY를 아니라면 SK를 출력합니다.