백준 9655번 돌 게임 (JAVA)

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

9655번: 돌 게임

 

저는 DP를 통해 문제를 풀었습니다.

DP를 통해 이전의 계산을 다시 하지 않도록하였고, 처음에 상근이 다음에 창영이가 번갈아가면서 하기 때문에 상근이가 이기면 창영이가 지고, 창영이가 이기면 상근이가 지기 때문에 다음으로 갈때 -1를 곱하여 문제를 풀었습니다.
(1이 승리 -1이 패배입니다.)

 

package BOJ.dp;

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

public class BOJ_9655 {
    private static final int WIN = 1;
    private static final int LOSE = -1;
    private static final int NOT_VALID = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        int result = cal(n,dp);
        if(result == WIN){
            System.out.println("SK");
        }else{
            System.out.println("CY");
        }
    }
    private static int cal(int depth,int[] dp){
        if(depth == 1){
            return WIN;
        }
        if(dp[depth] != NOT_VALID){
            return dp[depth];
        }
        int result = LOSE;
        result = Math.max(result,-cal(depth-1,dp));
        if(depth > 3){
            result = Math.max(result,-cal(depth-3,dp));
        }
        dp[depth] = result;
        return result;
    }
}