문제 접근

낼 수 있는 돌은 1,3,4 밖에없다는 것을 생각하고, 항상 턴은 상근이부터 시작한다는 것에 초점을 맞추자.

• N이 1인 경우 -> 승자: 상근, 케이스: 1
• N이 2인 경우 -> 승자: 창영, 케이스: 1 1
• N이 3인 경우 -> 승자: 상근, 케이스: 3
• N이 4인 경우 -> 승자: 상근, 케이스: 4
• N이 5인 경우 -> 승자: 상근, 케이스: 3 1 1
• N이 6인 경우 -> 승자: 상근, 케이스: 4 1 1
• N이 7인 경우 -> 승자: 창영, 케이스: 1 4 1 1, 3 4, 4 3

규칙을 찾아야 한다.
상근이는 항상 선이라는 것에 주목하면 쉽다.
현재 n개의 돌이 남았다고 생각해보자. 상근이가 x(x는 1,3,4 중 하나)개를 가져갔을때, 창영이가 1,3,4 개를 가져갔다고 생각해보자.
그러면, 남은 돌의 갯수는 n-x-1, n-x-3, n-x-4 가 된다.

• 이때, 남은 돌의 갯수를 기준으로 다시 게임을 시작한다고 생각하면 재귀구조로 생각해볼 수 있다. 즉, 게임의 돌 갯수 별로 dp라는 배열에 저장해놓고 있었다면 나중에 다시 끄집어내서 빠르게 게임 진행상태를 확인할 수 있다.
• 그렇다면 다시 본론으로 돌아가서, 남은 돌의 갯수인 n-x-1, n-x-3, n-x-4 에 대해서 모두 상근이가 이긴다면 즉, 상근이가 x개의 돌을 가져갔을때 창영이가 몇개를 가져가도 이길 수 없다면, 상근이는 x개 돌을 가져가면 그 게임을 승리하게 된다.

문제 풀이

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

class Main {
    static int N;
    static int[] size = new int[]{1, 3, 4};
    static String[] dp = new String[1001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        init();
        System.out.println(recursive(N));
    }

    private static String recursive(int n) { // 상영 턴 기준임.
        if (dp[n] != null) return dp[n];

        for (int sySize : size) {
            boolean allSY = true;
            for (int cySize : size) {
                int nextN = n - sySize - cySize;
                if ((nextN >= 0) && !recursive(nextN).equals("SK")) {
                    allSY = false;
                    break;
                }
            }

            // 상근이가 sySize를 냈을때, 
            // 찬영이가 뭘 내도 상근이가 다 이긴다면, 상근이는 이걸 내면 게임을 이긴다.
            if (allSY) {
                dp[n] = "SK";
                return dp[n];
            }
        }

        dp[n] = "CY";
        return dp[n];
    }

    private static void init() {
        Arrays.fill(dp, null);
        dp[0] = "CY";
        dp[1] = "SK";
        dp[2] = "CY";
        dp[3] = "SK";
        dp[4] = "SK";
        dp[5] = "SK";
    }
}

오랜만에 DP 푸니까 어려웠다.. ㅋㅋㅋ 다시 알고리즘 열심히 풀어야지.. 그동안 졸업을 위한 공인 어학 성적이랑 백엔드 공부 및 공모전 나가냐고 알고리즘 공부를 하지 못했다. 9월부터는 ict 인턴십을 하게 되어서 여기서 사용하는 기술스택 학습 및 알고리즘에만 집중할 계획이다. 올해는 꼭꼭 플레 달자