백준 9656 돌 게임 2 JAVA 풀이 (게임이론, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

돌 N개가 주어지고,
한 번에 1개 또는 3개의 돌을 가져갈 수 있다.

마지막 돌을 가져가는 사람이 승리할 때,
상근(SK)과 창영(CY) 중 누가 이기는지 출력하는 문제이다.

---

📌 접근 방법

이 문제는 단순 구현이 아니라
게임 이론 + 패턴 찾기 문제이다.

작은 값부터 직접 경우를 나열하면 규칙이 보인다.

---

📌 핵심 아이디어

N	결과
1	CY
2	SK
3	CY
4	SK
5	CY
6	SK

결과가 반복된다

• 홀수 → CY
• 짝수 → SK

---

왜 이런 결과가 나오나?

• 한 번에 1 또는 3을 가져가므로
• 상대를 **불리한 상태(홀수)**로 넘기면 승리 가능
• 짝수에서 시작하면 항상 이길 수 있음
• 홀수는 상대가 유리

---

📌 전체 코드

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

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

        System.out.println(N % 2 == 0 ? "SK" : "CY");
    }
}

---

📄 정리

• 게임 문제는 패턴 찾기가 핵심
• 작은 값부터 직접 써보는 것이 가장 빠름
• 이 문제는 짝수/홀수 패턴 문제