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

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

코드설명

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

 

문제에서 제일 중요한점은 두 사람이 완벽하게 게임했을 때의 의미에 대한 이해입니다.

각 DFS 분기점에서 만약 해당 사람이 이기는 경우가 있다면, 그 이기는 경우를 선택하도록 한다. 라는 의미입니다.

 

최적 부분 구조를 활용하여,

 

cache[stone]를 활용합니다.

• cache[stone] = 1: 돌이 stone개 남았을 때, 현재 차례인 플레이어가 이김
• cache[stone] = -1: 돌이 stone개 남았을 때, 현재 차례인 플레이어가 짐

예시로는,  cache[5] = 1로 저장되면, 돌이 5개 남은 모든 상황에서 이 값을 재사용합니다.

 

 

어려웠던 점은, game(level, stone)함수에서 level을 통해서 몇번째 플레이어가 플레이할지 결정하는데 이떄 cache[] 배열에 이 경우를 포함해야하나? 즉 2차원 배열로써 처리해야할까? 라는 생각이 들었습니다. 이유는, level 변수로 현재 몇번쨰 플레이가 플레이하는지 데이터를 가지고있기 떄문입니다.

확실하지는 않지만, level을 캐시하지 않는 이유는, 돌의 개수(stone)만 알면 누구의 턴인지 알 수 있기에 그렇습니다. 즉, stone이 홀수면 항상 상근의 턴, 짝수면 항상 창영의 턴입니다.

이러한 구조이기에 애초에 창영과 상근이의 cache[]가 겹치지 않는 것 같아 아래의 cache가 작동하는 것 같습니다. 

코드

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[N+1];
		Arrays.fill(cache, -2);
		System.out.println(game(0, N) < 0 ? "SK" : "CY");
	}
    
    public static int game(int level, int stone) {
    	if(stone == 1) {
    		//만약 1개 남은것을 선공이 가져간다면, 1을 반환합니다.
    		return (level % 2 == 0 ? 1 : -1);
    	}
    	if(cache[stone] != -2) return cache[stone];
    	
    	int bestScore;
    	//선공은, 1 이 반환되면 마지막 돌을 가져간 것 이라 생각한다.
    	if(level % 2 == 0) {
    		bestScore = Math.max(game(level + 1, stone - 1), stone >= 4 ? game(level + 1, stone - 3) : -2);
    	}
    	else {
    		bestScore = Math.min(game(level + 1, stone - 1), stone >= 4 ? game(level + 1 , stone - 3) : 2);
    	}
    	
    	return cache[stone] = bestScore;
    }
    
}