214. 카드 게임

백준

1. 다이나믹 프로그래밍

import sys
input = sys.stdin.readline

def dp(l, r):
  if r - l < 0: return
  if m[l][r]: return m[l][r]
  if r - l <= 1: #2장 남은 경우 큰 거
    m[l][r] = max(cards[l], cards[r])
    return  m[l][r]
  
  m[l][r] = cards[l] + min(dp(l + 2, r), dp(l + 1, r - 1)) #근우 왼쪽, 명우 왼쪽에서 선택 or 오른쪽 하나 선택
  m[l][r] = max(m[l][r], cards[r] + min(dp(l, r - 2), dp(l + 1, r - 1))) #왼쪽이랑 오른쪽 중 최적 선택
  
  return m[l][r]

for _ in range(int(input())):
  n = int(input())
  cards = list(map(int, input().split()))
  m = [[0] * (n) for _ in range(n)] #i~j구간의 최선 전략에서 근우 점수
  answer = dp(0, n - 1)
  print(answer)

2. C++

#include <cstdio>
#include <algorithm>
#include <memory.h>
#define MAX 1005
using namespace std;
int n, k;
int a[MAX], m[MAX][MAX];

int dp(int l, int r){
  if(r - l < 0) return 0;
  if(m[l][r]) return m[l][r];
  if(r - l <= 1){
    m[l][r] = max(a[l], a[r]);
    return m[l][r];
  }
  m[l][r] = a[l] + min(dp(l + 2, r), dp(l + 1, r - 1));
  m[l][r] = max(m[l][r], a[r] + min(dp(l, r - 2), dp(l + 1, r - 1)));
  
  return m[l][r];
}

int main(){
  int t;
  scanf("%d", &t);
  while(t--){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
      scanf("%d", a + i);
    }
    memset(m, 0, sizeof(m));
    int ans = dp(0, n - 1);
    printf("%d\n",ans);
  }
}