[BaekJoon] #9660 - 돌 게임 6 [Java][C++]

문제 링크

---

1. 아이디어

BaekJoon 9657번 - 돌 게임 3 문제에서 $N$이 최대 $10^{12}$까지 커진 문제로, 이전처럼 dp 표를 채울 수 없으니 승패의 반복 규칙을 찾아야 한다. 돌이 0개인 상태를 지는 자리(L)로 두고 이전 문제의 점화식으로 차례로 구하면 승패가 L, W, L, W, W, W, W 순서로 나오고, 인덱스 7부터 다시 L, W, L, W가 나온다. 이 점화식은 바로 앞 네 칸의 값에만 의존하므로 연속한 네 칸의 값이 한 번 반복되면 그 뒤도 같은 순서로 반복되고, 따라서 승패는 7을 주기로 반복된다. 결국 $N$을 7로 나눈 나머지가 0 또는 2이면 상근이가 지고 창영이가 이기며, 그 외에는 상근이가 이긴다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++]

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 % 7 == 0 || n % 7 == 2) {
            System.out.println("CY");
        } else {
            System.out.println("SK");
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long n;
    cin >> n;

    if (n % 7 == 0 || n % 7 == 2) {
        cout << "CY";
    } else {
        cout << "SK";
    }
}

---