백준 11062 : 카드 게임

문제 링크

최선의 전략을 그리디로 짜보려고 했는데 어려움이 있었다. 그래서 DP를 이용해서 문제를 해결하였다. dp[i][j] = 근우의 턴에서 i~j까지 카드가 남았을 때 근우가 가질 수 있는 최대 점수라고 정의한다. 근우와 명우의 턴을 같이 계산하면서 dp를 전개해 나갈껀데, 근우는 자신의 점수를 최대로 만드려고 할 것이고, 명우는 근우의 점수를 최소로 만드려고 할 것이다. 따라서, dp는

dp[i][j] = max(vec[i] + min(dp[i+2][j],dp[i+1][j-1]))
dp[i][j] = max(dp[i][j],vec[j] + min(dp[i+1][j-1],dp[i][j-2]))

로 나타낼 수 있다. min 부분은 명우의 선택을 의미하고, max는 근우의 선택을 의미한다. 기저상황은 i > j이면 0, i == j 이면 vec[j]이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

vector<vector<int>> dp;
vector<int> vec;

int solve(int from,int to)
{
    if(from > to) return 0;

    int& cur = dp[from][to];

    if(cur != -1) return cur;

    if(from == to) return cur = vec[from];

    cur = min(vec[from] + solve(from+2,to),vec[from] + solve(from+1,to-1));
    cur = max(cur,min(vec[to] + solve(from+1,to-1),vec[to] + solve(from,to-2)));

    return cur;
} 

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        dp = vector<vector<int>>(n,vector<int>(n,-1));
        vec = vector<int>(n);
        
        for(int i = 0;i<n;i++)
        {
            cin>>vec[i];
        }

        cout<<solve(0,n-1)<<"\n";
    }

    return 0;
}