[백준] 9658 돌 게임 4 - 동적계획법(DP, Dynamic Programming) + 게임이론(Game Theory) JAVA

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

코드설명

동적계획법(DP, Dynamic Programming) + 게임이론(Game Theory)을 활용합니다.

 

고민했었던점은, Cache에서 초기값을 -3말고 -2나 2로 두어도 괜찮을까? 라는 생각이 있었습니다.

가능합니다. 이유는, 해당 -2와 2가 이미 "불가능한 경우"를 의미하기 때문입니다.

그렇지만, 좀 더 명확한 표현을 위해 cache에서 초기값을 둘 때 -2와 2를 사용하지 않고, -3을 사용하여 한번도 계산되지 않음을 표현합니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, M;
    private static int answer = 0;
    private static int[][] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		cache = new int[2][N+1];
		for(int i=0;i<=1;i++) {
			Arrays.fill(cache[i], -3);
		}
		answer = game(0, N);
//		System.out.println(answer);
		System.out.println(answer > 0 ? "SK" : "CY");
	}
    
    public static int game(int level, int stones) {
    	//만약 돌이 없는 상태라면, 게임이 끝난상태다.
    	if(stones <= 0) {
    		//만약 선공차례에 돌이 없는상태라면, 선공이 이긴다.
    		return level % 2 == 0 ? 1 : -1;
    	}
    	if(cache[level%2][stones] != -3) return cache[level%2][stones];
    	
    	//만약 선공차례라면,
    	int bestChoice;
    	if(level % 2 == 0) {
    		int ret1 = -2, ret2 = -2, ret3 = -2;
    		
    		if(stones >= 1)
    			ret1 = game(level + 1, stones -1);
    		if(stones >= 3)
    			ret2 = game(level + 1, stones - 3);
    		if(stones >= 4)
    			ret3 = game(level + 1, stones - 4);
    		
    		bestChoice = Math.max(ret1, Math.max(ret2, ret3));
    	}
    	
    	else {
    		int ret1 = 2, ret2 = 2, ret3 = 2;
    		if(stones >= 1)
    			ret1 = game(level + 1, stones -1);
    		if(stones >= 3)
    			ret2 = game(level + 1, stones - 3);
    		if(stones >= 4)
    			ret3 = game(level + 1, stones - 4);
    		
    		bestChoice = Math.min(ret1, Math.min(ret2, ret3));
    	}
    	return cache[level%2][stones] = bestChoice;
    	
    }
    
}

 

더 깔끔하게 해결할 수 있습니다. 위의 코드는 현재 턴제 기반으로 게임을 진행하고 있어서 각 턴들을 저장하고 있습니다.

하지만, return -ret; 형식처럼 마이너스 값으로 부호를 변형시켜서 반환시킴으로써 턴제 게임에서의 턴을 표현할 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		cache = new int[N+1];
		Arrays.fill(cache, -2);
		System.out.println(game(N) == 1 ? "SK" : "CY");
		
	}
	static int game(int N) {
		//만약 마지막 돌을 가져가야할 경우 이 사람이 진것이다.
		if(N == 1) {
			return -1;
		}
		
		if(cache[N] != -2) return cache[N];
		
		int ret;
		ret = game(N - 1);
		
		if(N-3 >= 1)
			ret = Math.min(ret, game(N-3));
		if(N-4 >= 1){
			ret = Math.min(ret, game(N-4));
		}
		
		return cache[N] = -ret;
	}
	
	
	
}