[DP] BOJ 11062 카드 게임 (C++)

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

11062번: 카드 게임

 

문제 해결 알고리즘

 

근우는 더 큰 카드를 갖고 점수를 최대로 하고, 명우는 근우의 점수가 최소로 되는 방향으로 플레이 해야한다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int arr[1001], dp[1001][1001];

int cardgame(int left, int right, int turn){

    if(left > right) return 0;
    if(dp[left][right]) return dp[left][right];

    if(turn % 2) return dp[left][right] = max(arr[left] + cardgame(left+1, right, turn+1), 
    arr[right] + cardgame(left, right-1, turn+1));

    else return dp[left][right] = min(cardgame(left+1, right, turn+1), 
    cardgame(left, right-1, turn+1));
    
}

int main(){
    int T; cin >> T;

    while(T--){
        int N; cin >> N;

        for(int i=0;i<N;i++) cin >> arr[i];
        
        cardgame(0, N-1, 1);
        
        cout << dp[0][N-1] << '\n';

        memset(dp, 0, sizeof(dp));

    }
}