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

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

코드설명

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

 

완벽한 게임을 한다는 가정으로 문제를 풀어나가면 됩니다.

 

처음에 틀렸었던 테스트케이스입니다.

테스트 케이스 

입력 1

4

출력 1

SK

 

처음에 돌 1개가 남았을때 선공차례라면, 선공이 마저 먹으면 되니 1을 반환하도록 할려고 했습니다.

하지만, 생각해보면 돌이 4개일경우, 4개의 돌게임을 했을떄 돌이 0개가 되어 올바르게 처리되지 않습니다.

코드

코드 1 입니다

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 {
    public static int N, T, M; 
    public static int answer = 0;
    public 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<2;i++) {
			Arrays.fill(cache[i], -2);
		}
		int answer = game(0, N);
		System.out.println(answer > 0 ? "SK" : "CY");
	}
    
    public static int game(int level, int stone) {
    	if(stone <= 0) {
    		//만약 돌을 모두 가진 상태에서 선공차례로 온다면, 선공이 진것이므로 -1 입니다.
    		return (level % 2 == 0) ? -1 : 1;
    	}
//    	if(cache[level][stone] != -2) return cache[level][stone];
    	if(cache[level % 2][stone] != -2) return cache[level % 2][stone];
    	
    	int bestScore;
    	//선공 차례일경우
    	if(level % 2 == 0) {
    		int ret1 = -2, ret2 = -2, ret3 = -2;
    		ret1 = game(level + 1, stone - 1);
    		if(stone >= 3) ret2 = game(level + 1, stone - 3);
    		if(stone >= 4) ret3 = game(level + 1, stone - 4);
    		bestScore = Math.max(ret1, Math.max(ret2, Math.max(ret3, -2)));
    	}
    	else {
    		int ret1 = 2, ret2 = 2, ret3 = 2;
    		ret1 = game(level + 1, stone - 1);
    		if(stone >= 3) ret2 = game(level + 1, stone - 3);
    		if(stone >= 4) ret3 = game(level + 1, stone - 4);
    		bestScore = Math.min(ret1, Math.min(ret2, Math.min(ret3, 2)));
    	}
    	return cache[level % 2][stone] = bestScore;
    }
    
    
}

 

처음에 틀린 코드입니다. 만약 돌이 4개 존재했을시, 4개 모두 가져간다면 돌이 0개가 남는다는 것을 생각하면 수정할 수 있습니다.

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 {
    public static int N, T, M; 
    public static int answer = 0;
    public 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<2;i++) {
			Arrays.fill(cache[i], -2);
		}
		int answer = game(0, N);
		System.out.println(answer > 0 ? "SK" : "CY");
	}
    
    public static int game(int level, int stone) {
    	if(stone == 1) {
    		//만약 마지막 돌을 선공이 가져간다면, 1을 반환한다.
    		return (level % 2 == 0) ? 1 : -1;
    	}
//    	if(cache[level][stone] != -2) return cache[level][stone];
    	if(cache[level % 2][stone] != -2) return cache[level % 2][stone];
    	
    	int bestScore;
    	//선공 차례일경우
    	if(level % 2 == 0) {
    		int ret1 = -2, ret2 = -2, ret3 = -2;
    		ret1 = game(level + 1, stone - 1);
    		if(stone >= 4) ret2 = game(level + 1, stone - 3);
    		if(stone >= 5) ret3 = game(level + 1, stone - 4);
    		bestScore = Math.max(ret1, Math.max(ret2, Math.max(ret3, -2)));
    	}
    	else {
    		int ret1 = 2, ret2 = 2, ret3 = 2;
    		ret1 = game(level + 1, stone - 1);
    		if(stone >= 4) ret2 = game(level + 1, stone - 3);
    		if(stone >= 5) ret3 = game(level + 1, stone - 4);
    		bestScore = Math.min(ret1, Math.min(ret2, Math.min(ret3, 2)));
    	}
    	return cache[level % 2][stone] = bestScore;
    }
    
    
}