백준 9658번 돌 게임4 (JAVA)

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

9658번: 돌 게임 4

 

저는 해당 문제를 DP를 통해 해결하였습니다.

DP를 통해 해당 숫자일 때 최선을 다했을 때 이길 수 있는지 없는지를 저장하였습니다.

result에 넣을 때 이전 값의 음수를 넣는 이유는 내가 돌을 가져가면 상대방 차례로 돌아가기 때문에 전의 결과의 반대로 해주어야 합니다.

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_9658 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[] dp = new int[n+1];
        if(cal(n,dp) == WIN){
            System.out.println("SK");
        }else{
            System.out.println("CY");
        }
    }
    private static final int NOT_VALID = 0;
    private static final int WIN = 1;
    private static final int LOSE = -1;
    private static int cal(int n, int[] dp) {
        if(n == 1){
            return LOSE; // SK가 지는 것
        }
        if(dp[n] != NOT_VALID){
            return dp[n];
        }
        int result = LOSE;
        for(int i = 1 ; i <= 4 ; i++){
            if(i == 2){
                continue;
            }
            if(n - i <= 0){
                break;
            }
            result = Math.max(result,-cal(n-i,dp) );
        }
        dp[n] = result;
        return result;
    }
}