[백준 11062 - JAVA] 카드 게임

11062번: 카드 게임

정말정말 DP는 풀 때마다 모르겠다!

결국 블로그를 참고해서 어떻게 푸는지 보고 풀었다.

최선의 전략으로 진행하는 것이기 때문에 모든 경우를 확인해야하고,
DP를 이용해 각 턴마다 근우가 높은 점수를 얻는 경우와 명우가 낮은 점수를 얻는 경우를 저장해둔다. 

그래서 DP배열은 [근우와 명우의 턴][시작 카드(왼쪽 끝)의 인덱스][마지막 카드(오른쪽 끝)의 인덱스]로 크기는 [2][N][N]으로 할당한다!

 

풀이 방법

1. DP배열의 초기값을 -1로 넣어준다.
2. 턴은 근우부터 0, 시작은 0, 마지막은 N-1
3. DP에 저장된 값이 없는 경우(-1)에는 근우의 턴에서는 높은 점수를 가져가는 경우를,
   명우의 턴에서는 낮은 점수를 가져가는 경우를 저장한다.
4. DP의 초기값(-1)이 아니라 저장된 값이 있는 경우에는 저장되어있는 값을 바로 반환한다.
5. 카드의 시작과 끝이 같은 경우에는 한장이 남은 경우로 남은 턴에 따라 근우 점수에 더하거나 0을 반환해준다 (명우가 가진 경우)

import java.io.*;
import java.util.*;

public class Main {
	public static int N;
	public static int[] cards;
	public static int[][][] dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			N = Integer.parseInt(br.readLine());
			cards = new int[N];
			st = new StringTokenizer(br.readLine());;
			for (int i = 0; i < N; i++) {
				cards[i] = Integer.parseInt(st.nextToken());
			}
			
			dp = new int[2][N][N];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < N; j++) {
					Arrays.fill(dp[i][j], -1);
				}
			}
			System.out.println(solve(0, 0, N-1));
		}
	}
	
	public static int solve(int turn, int start, int end) {
		if (dp[turn][start][end] != -1) {
			return dp[turn][start][end];
		}
		
		if (start == end) {
			if (turn == 0) return cards[start];
			else return 0;
		}
		
		dp[turn][start][end] = 0;
		if (turn == 0) {
			dp[turn][start][end] = Math.max(solve(1, start + 1, end) + cards[start], solve(1, start, end - 1) + cards[end]);
		} else { 
			dp[turn][start][end] = Math.min(solve(0, start + 1, end), solve(0, start, end - 1));
		}
		return dp[turn][start][end];
	}
}