BOJ 9657 - 돌 게임 3

문제

BOJ 9657 - 돌 게임 3

돌 게임 3은 두 명이서 즐기는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 돌을 가져가는 게임을 하는데, 돌은 1, 3, 4개 중 하나를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임에서 이기게 된다. 두 사람이 모두 최선을 다해 게임을 한다면, 상근이가 이기면 SK, 창영이가 이기면 CY를 출력하라. 상근이가 먼저 시작한다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

상근이가 이기면 SK, 창영이가 이기면 CY를 출력한다.

예제

입력:

4

출력:

SK

풀이

핵심 아이디어: 소수의 N에 대해 직접 DP로 계산하면 N=1~7의 패턴을 구할 수 있다. 1→SK, 2→CY, 3→SK, 4→SK, 5→SK, 6→CY, 7→SK. 이 7개 주기로 패턴이 반복된다. N % 7 == 0 또는 N % 7 == 2일 때만 CY(창영 승리), 나머지는 SK(상근 승리)이다.

1. 소규모 DP 분석: dp[i]를 true(현재 플레이어 승) / false(패)로 정의한다.
   • dp[1] = true (1개 가져가면 승리)
   • dp[2] = false (1, 3, 4 중 어느 것도 남은 돌을 처리할 수 없어 다음 플레이어가 승리)
   • dp[3] = true, dp[4] = true, dp[5] = true, dp[6] = false, dp[7] = true
2. 주기 발견: dp[i]는 dp[i-1], dp[i-3], dp[i-4] 중 하나라도 false면 true이다. 이 규칙으로 계산 시 N % 7 == 0 또는 N % 7 == 2 패턴이 나온다.
3. O(1) 결론: N이 최대 10억이므로 DP 대신 수학적 패턴을 직접 사용한다.

코드

package ASP_study.day299;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Day293BOJ9657돌게임수학 {
	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 == 0 || N % 7 == 2) ? "CY" : "SK");
		bw.flush();
		bw.close();
		br.close();
	}
}

복잡도

• 시간: O(1) — N % 7 연산만 수행
• 공간: O(1)