BOJ 9658 - 돌 게임 4

문제

N개의 돌을 두 사람이 번갈아 가져가며 (1, 3, 4개 가능), 마지막 돌을 가져가는 사람이 지는 게임에서 선공(SK)의 승리 여부를 판별하라.

입력

N이 주어진다.

출력

선공이 이기면 "SK", 지면 "CY"를 출력한다.

예제

입력	출력
`6`	`SK`

풀이

패턴을 분석하여 N mod 7로 승패를 판별한다.

N mod 7이 1 또는 3이면 후공(CY) 승리
그 외에는 선공(SK) 승리

핵심 아이디어: 게임 이론에서 Grundy 값의 패턴이 주기 7로 반복되며, N%7==1 또는 3일 때만 선공이 진다.

코드

package day499;
 
import java.io.*;
 
public class Day479BOJ9658돌게임4 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int N = Integer.parseInt(br.readLine());
 
    bw.write((N % 7 == 1 || N % 7 == 3) ? "CY" : "SK");
    bw.flush();
    bw.close();
    br.close();
  }
}

복잡도

시간: O(1)
공간: O(1)

문제