[ 백준 / C++ ] 11062 : 카드 게임

[ 문제 ]

 

11062번: 카드 게임

 

[ 접근방법 ]

 

두 사람이 번갈아 가며 양 끝 중 하나의 숫자를 고르는 게임으로, 고른 숫자의 합이 상대편보다 높도록 행동해야 한다.

 

여기서 중요한 점은 나 뿐만 아니라 상대편도 최대 점수를 얻기 위해 최적의 행동을 한다는 점이다.

상대편이 최대 점수를 얻기 위해 하는 행동은 내가 최소 점수를 얻기 위해 하는 행동과 같다.

이를 dp에 반영하면 쉽게 문제를 해결할 수 있다.

 

dp[ i ][ j ] =  i ~ j 구간에서 현재 플레이어가 얻을 수 있는 최대 점수

 

i ~ j  구간에서는 왼쪽(i)과 오른쪽(j)을 고르는 선택지가 있다.

만약 i를 선택하면, 상대는 i + 1 또는 j 중 최소 점수를 유도하는 것을 선택할 것이다.

만약 j를 선택하면, 상대는 i 또는 j - 1 중 최소 점수를 유도하는 것을 선택할 것이다.

 

dp[ i ][ j ] = max(left, right) 를 구간을 넓혀가며 진행하면 된다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; i++) cin >> arr[i];

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int i = 1; i <= n; i++) dp[i][i] = arr[i];
        for (int l = 2; l <= n; l++)
        {
            for (int i = 1; i <= n - l + 1; i++)
            {
                int j = i + l - 1;

                int left = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]);
                int right = arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2]);

                dp[i][j] = max(left, right);
            }
        }
        cout << dp[1][n] << "\n";
    }

    return 0;
}