(11062) 카드 게임

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

단계별로 풀어보기

31단계(동적 계획법 2) 7번째

 

 

 

이것도 정말 어려운 DP문제다. dp를 정의하는 것부터 난관이다.

dp[a][b]를 a번째 카드부터 b번째 카드까지 남았을 때 지금 차례인 사람이 얻을 수 있는 점수의 최대값이라고 하자.

dp[x][x]는 현재 차례인 사람이 그 카드를 가져가고 게임이 끝나므로 x번째 카드의 값과 같다.

dp[x][y] 상태에서, 현재 플레이어는 x번째 카드 또는 y번째 카드를 가져갈 수 있다.

이때 상대방이 얻는 점수는 dp[x+1][y] 또는 dp[x][y-1]이다. 최선의 선택을 한다면 이 값을 최소화할 것이다.

따라서 dp[x][y]= (지금 상태에서 가능한 점수 총합)-min(dp[x+1][y], dp[x][y-1])이다.

지금 상태에서 가능한 점수 총합은 x번째 카드부터 y번째 카드까지 부분합이다.

dp를 현재 차례인 사람이 얻는 점수의 최대값으로 정의했으므로, N의 홀짝 여부에 관계없이 dp[1][N]이 답이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int solve(){
  int n;
  
  cin >> n;
  
  vector<int> s(n+1);
  vector dp(n+1, vector<int>(n+1));
  
  for(int i=1;i<=n;i++){
    cin >> s[i];
    
    dp[i][i]= s[i];
    s[i]+= s[i-1];
  }
  
  for(int i=1;i<n;i++){
    for(int j=1;j+i<=n;j++){
      dp[j][j+i]= s[j+i]-s[j-1]-min(dp[j+1][j+i], dp[j][j+i-1]);
    }
  }
  
  return dp[1][n];
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}