문제

아이디어

게임 이론 문제다. 일단 N=k일 때를 가정해 일반화해보자.

f(x) = 돌이 x개일 때 선택권을 가진 플레이어의 승리 경우의 수 존재 여부라고 가정하자.

이 때, f(k) = false라면 f(k-1) = f(k-3) = f(k-4) = true를 만족해야 한다.

돌이 k개있을 때, 1, 3, 4개 중 어느 경우를 선택하더라도 상대방이 이기는 경우의 수만 존재할 때이며, 그 반대는 반드시 f(k) = true가 된다.

점화식은 f(k) = !(f(k-1) && f(k-3) && f(k-4)) (k > 4})가 된다.

점화식을 알아냈으니 N=1부터 f(k)를 구하며 주기를 알아보자.

N = 1일 때, 플레이어가 돌을 1개 가져오면 승리하므로 f(1) = true
N = 2일 때, 플레이어가 돌을 1개 가져올 수밖에 없고, f(1) = true이므로 f(2) = false
N = 3일 때, 플레이어가 돌을 3개 가져오면 승리하므로 f(3) = true
N = 4일 때, 플레이어가 돌을 4개 가져오면 승리하므로 f(4) = true
N = 5일 때, 플레이어가 돌을 3개 가져오면 f(2) = false이므로 f(5) = true
N = 6일 때, 플레이어가 돌을 4개 가져오면 f(2) = false이므로 f(6) = true
N = 7일 때, f(6) = true, f(4) = true, f(3) = true이므로 f(7) = false
N = 8일 때, 플레이어가 돌을 1개 가져오면 f(7) = false이므로 f(8) = true
N = 9일 때, f(8) = true, f(6) = true, f(5) = true이므로 f(9) = false
...

위와 같이 쭉 전개하다보면 arr[i] = f(i)인 배열 arr는 아래와 같은 결과를 갖는다.

arr = [F, T, F, T, T, T, T, F, T, F, T, T, T, T, F, T, F, ...]

3~9, 10~16, ... 요소들이 T, T, T, T, F, T, F의 패턴을 갖는걸 확인했다.
이를 통해 답을 구할 수 있겠다.

소스코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());

        if(N == 1) System.out.println("SK");
        else if(N == 2) System.out.println("CY");
        else {
            int flag = (int) ((N-3) % 7L);
            if(flag == 4 || flag == 6)
                System.out.println("CY");
            else
                System.out.println("SK");
        }
    }
}

채점결과