[백준/9658] 돌 게임 4 - JAVA

이지환·2025년 3월 26일

백준 알고리즘

알고리즘(백준) 💻

목록 보기

49/80

📌 문제

알고리즘 분류 : DP
난이도 : 실버2
출처 : 백준 - 돌 게임 4

🦧 문제 풀이 접근

DP 알고리즘을 사용해서 풀이한다.
마지막 돌을 뽑으면 진다는 뜻은 곧 마지막-1 번째 돌을 뽑는 사람이 이긴다는 뜻이다.
이때 가장 중요한 포인트는 상근이가 먼저 게임을 시작하기 때문에 상근이가 최대한 유리하게 숫자를 뽑을 수 있다.

dp배열에 -1, -3, -4번째 돌을 전부다 상근이가 뽑은 경우 다음 돌은 찬영이가 뽑기때문에 찬영이의 승리이다.
그 외에 경우 상근이가 승리한다.

💻 code

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 num = Integer.parseInt(br.readLine());
        boolean dp[] = new boolean[1001];
        //false == SK, true == CY
        dp[1] = true;
        dp[2] = false;
        dp[3] = true;
        dp[4] = false;
        for(int i=5;i<=num;i++) {
            if(!dp[i-1]&&!dp[i-3]&&!dp[i-4])
                dp[i] = true;
            else
                dp[i] = false;
        }
        System.out.println(dp[num]?"CY":"SK");
    }
}