11062 카드 게임

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

11062번: 카드 게임

N이 1000이기 때문에 브루트포스를 수행하면 2^500으로 시간초과가 난다. 어떻게 연산을 줄일 수 있을까 고민하다 다이나믹 프로그래밍까지 떠올리긴 했지만 점화식을 세우기 어려웠다.

우선 이 문제는 모든 경우의 수를 탐색해야 한다. 왼쪽과 오른쪽을 고른 경우가 각각 최대 점수를 얻는게 달라지기 때문이다. 즉, 근우의 차례엔 근우의 점수가 최대가 되게 하고, 명우의 차례엔 근우의 점수가 최소가 되도록 해야 한다.

문제의 조건을 유심히 보면 부분 문제가 있는걸 알 수 있는데, dp[l][r] = l~r번째 카드 중에서 근우가 얻을 수 있는 최대 점수로 테이블을 구성하여 이미 구한 값을 재사용하도록 했다.

import java.io.*;
import java.util.*;
public class Main {
  public static int T, N;
  public static int[] card;
  public static int[][] dp;
  public static int Game(int l, int r, int t){
    if(l > r) return 0;
    if(dp[l][r] != 0) return dp[l][r];

    if(t % 2 != 0)
      return dp[l][r] = Math.max(card[l] + Game(l + 1, r, t + 1), card[r] + Game(l, r - 1, t + 1));
    else
      return dp[l][r] = Math.min(Game(l + 1, r, t + 1), Game(l, r - 1, t + 1));
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    T = Integer.parseInt(st.nextToken());
    while(T-- != 0){
      st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      card = new int[N]; dp = new int[N][N];
      st = new StringTokenizer(br.readLine());
      for(int i = 0; i < N; i++)
        card[i] = Integer.parseInt(st.nextToken());
      System.out.println(Game(0, N - 1, 1));
    }
  }
}