https://www.algospot.com/judge/problem/read/NUMBERGAME
algospot.com :: NUMBERGAME
숫자 게임 문제 정보 문제 n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지
www.algospot.com
코드설명
동적계획법(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;
}
}