[BOJ] 9657. 돌 게임 3 (🥈, DP)

🔗

풀이

완벽하게 게임 한다 = 서로 이길 수 있는 패만 선택한다

상근이가 항상 먼저 시작하고, 상근이나 창영이는 어떤 패를 두든 자신이 이길 수 있는 패를 선택하게 된다.

우선 돌은 1,3,4개를 한 번에 가져갈 수 있으므로 주어지는 돌의 개수가 1,3,4 중 하나라면 무조건 먼저 시작하는 상근이가 이기게 된다.

하지만 돌의 개수를 넘어서는 만큼 가져갈 수는 없기 때문에 돌의 개수가 2개로 주어진다면 먼저 시작하는 상근이는 돌의 개수보다 적은 1개를 가져가게 되고, 그 다음으로 창영이가 1개를 가져가게 되면서 창영이가 이기게 된다.

결국 이 문제는 돌의 개수를 넘어서지 않는 만큼 가져가면서 최대한 자신이 이길 수 있는 방향으로 게임을 전개해서 누가 이기는지 판단하는 것이다.

돌이 5개 인 경우

상근이가 1개를 가져가는 경우

돌은 4개가 남게 된다. 차례는 창영이에게 넘어가게 되고 4개를 한꺼번에 가질 수 있으므로 창영이가 우승하게 된다.

상근이가 3개를 가져가는 경우

돌은 2개가 남게 된다. 차례가 창영이에게 넘어가지만 창영이는 1개밖에 가져갈 수 없다. 다시 차례는 상근이에게 넘어오게 되고 상근이가 우승하게 된다.

상근이가 4개를 가져가는 경우

돌은 1개가 남게 된다. 창영이가 1개를 가면서 우승하게 된다.

DP 점화식 찾기

각 돌에 대해 몇 개의 턴이 이루어지면 게임이 종료되는지에 대한 정보를 기록하면 된다. 1,3,4의 경우 모두 한 번의 턴만 지나면 게임이 종료될 수 있으므로 1이다. 2의 경우 반드시 2번의 턴이 돌아야 하므로 2이다.

5의 경우부터는 시작하는 사람의 의지에 달리게 되는데 상근이는 반드시 자신이 이기는 쪽으로 게임을 진행하려고 하게 된다. 1개나 4개를 가져가게 되면 4개가 남거가 1개가 남기 때문에 게임이 한 턴만에 종료된다. 그렇게 되면 상근이에게 불리하기 때문에 상근이는 최대한 게임이 2턴 넘게 남은 경우를 택하게 된다. 그 중에서도 짝수로 남아야 자신에게 다시 기회가 돌아온다. 즉 3개를 가져가고 2개를 남는 경우를 택하게 된다.

이런 방식으로 1부터 n까지 진행되는 턴의 개수를 찾게 된다. 홀수라면 상근이가, 짝수라면 창영이가 우승하게 된다. 현재 게임을 진행하는 입장에서는 자신이 가져가고 남는 돌의 개수에 적혀 있는 턴의 수가 짝수여야 자신에게 다시 턴이 돌아오게 되기 때문에 그쪽으로 게임을 진행하려 하게 된다. 돌의 개수가 i 라고 할 때, i-1, i-3, i-4 에 적혀있는 턴의 수가 짝수번이라면 현재 돌의 개수에는 홀수번을 기록하고, 아니라면 짝수번을 기록한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

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());

        int[] dp = new int[n+4];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 1;
        dp[4] = 1;

        for (int i = 5; i < n+1; i++) {
            if (dp[i-1] == 2 || dp[i-3] == 2 || dp[i-4] == 2) {
                dp[i] = 1;
            } else {
                dp[i] = 2;
            }
        }

        if (dp[n] == 2) {
            System.out.println("CY");
        } else {
            System.out.println("SK");
        }
    }
}