[백준 JAVA] 9655 돌 게임

9655 돌 게임

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

문제설명

플레이어 두 명이 번갈아가며 돌을 하나씩 또는 셋씩 빼는 게임을 하고 있다.

돌이 없어서 더 이상 돌을 뺄 수 없는 사람이 진다고 했을 때

주어진 돌의 개수 N에서 시작 플레이어가 승리할 수 있는지를 구한다.

접근방식

O(N)  시간복잡도

 

동적 프로그래밍은 상수 시간이 소요된다. 

 

문제 조건 분석 과정

• 두 명의 플레이어(SK와 CY)가 번갈아가며 돌을 제거한다.
• 플레이어는 한 번의 턴에 1개 또는 3개의 돌을 제거할 수 있다.
• 돌이 더 이상 남지 않은 상태에서 턴이 오면 그 플레이어는 패배한다.

동적 프로그래밍(DP)을 사용하여 문제를 해결한다.

배열 dp를 사용하여 dp[i]가 true이면 돌이 i개일 때 SK가 승리이다.

• dp[1] = true: 돌이 1개일 때 SK가 승리
• dp[2] = false: 돌이 2개일 때 CY가 승리
• dp[3] = true: 돌이 3개일 때 SK가 승리

전체코드

import java.util.*;
import java.io.*;

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());
        String result = solve(N);

        System.out.println(result);
    }

    private static String solve(int N) {
        // N이 0일 때, dp 배열이 범위를 넘어서는 것을 방지하기 위해 N + 1 크기의 배열을 생성
        boolean[] dp = new boolean[N + 1];

        // 초기 상태 설정
        if (N >= 1) dp[1] = true;  // 1개의 돌을 가지고 있을 때 SK가 승리 (SK가 첫 턴에 돌을 가져가면 CY가 남은 돌로 플레이할 수 없음)
        if (N >= 2) dp[2] = false; // 2개의 돌을 가지고 있을 때 CY가 승리 (SK가 1개 돌을 가져가면 CY가 남은 1개 돌로 플레이할 수 있음)
        if (N >= 3) dp[3] = true;  // 3개의 돌을 가지고 있을 때 SK가 승리 (SK가 1개 돌을 가져가면 CY가 2개 돌로 플레이할 수 없고, 3개 돌을 가져가면 CY가 플레이할 수 없음)

        // dp 배열을 사용하여 각 상태의 승리 여부를 결정
        for (int i = 4; i <= N; i++) {
            // 현재 i개의 돌에서 SK가 이길 수 있는지를 판단
            // dp[i]가 true라면, SK가 이길 수 있다는 뜻
            // dp[i]는 현재 상태에서 이전 상태(1개 또는 3개 돌을 가져갔을 때)의 승리 여부를 바탕으로 결정
            // 현재 상태에서 SK가 승리하기 위해서는 이전 상태에서 CY가 승리할 수 있어야 함
            // 즉, dp[i]는 이전 상태 중 하나라도 CY가 패배하는 경우가 있을 때 true로 설정
            dp[i] = !dp[i - 1] || !dp[i - 3];
        }

        // 결과를 반환
        return dp[N] ? "SK" : "CY";
    }
}