[종만북][알고스팟] NUMBERGAME(숫자게임) - 동적계획법(Dynamic Programming, DP) + 게임이론(Game Theory) JAVA

https://www.algospot.com/judge/problem/read/NUMBERGAME

algospot.com :: NUMBERGAME

코드설명

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

 

각 선택당 최적의 선택,즉, 다음 선수와의 연산차이가 MAX의 차이를 낼 수 있는 선택을 계속해서 진행함으로써, 게임을 진행해나갑니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int C, N, W, H, K;
    private static int answer = 0;
    private static int[] arr;
    private static int[][] cache;
    private static final int EMPTY = -987654321;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        C = Integer.parseInt(st.nextToken());
        while(C-- > 0){
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	arr = new int[N];
        	cache = new int[N][N];
        	for(int i=0;i<N;i++) {
        		Arrays.fill(cache[i], EMPTY);
        	}
        	st = new StringTokenizer(br.readLine());
        	for(int i=0;i<N; i++) {
        		arr[i] = Integer.parseInt(st.nextToken());
        	}
        	
        	System.out.println(play(0, N - 1));
        }
        
    }
    
    private static int play(int left, int right) {
    	//기저사례: 모든 수가 다 없어졌을때
    	if(left > right) return 0;
    	
    	//메모이제이션
    	if(cache[left][right] != EMPTY) return cache[left][right];
    	
    	//수를 가져가는 경우
    	int ret = Math.max(arr[left] - play(left + 1, right), arr[right] - play(left , right - 1));
    	
    	//수를 없애는 경우
    	if(right - left + 1 >= 2) {
    		ret = Math.max(ret,  -play(left + 2, right));
    		ret = Math.max(ret,  -play(left, right - 2));
    	}
    	
    	return cache[left][right] = ret;
    }
    
    
}