[백준 11062번] 카드 게임 (C++)

문제링크 : https://www.acmicpc.net/problem/11062

11062번: 카드 게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N;
int arr[1001];
int dp[1001][1001][2]; //l, r, 차례

int func(int l, int r, int t) //0 근우, 1 명우
{
    if(dp[l][r][t]!=-1) return dp[l][r][t]; //중복계산 방지
    if(l==r) //남은 카드 한장
    {
        if(!t) return dp[l][r][t] = arr[l]; //근우 get
        else return dp[l][r][t] = 0; //명우 get
    }

    if(!t) dp[l][r][t] = max(func(l+1, r, 1)+arr[l], func(l, r-1, 1) + arr[r]); //왼쪽 or 오른쪽 근우 최대
    else dp[l][r][t] = min(func(l+1, r, 0), func(l, r-1, 0)); //왼쪽 or 오른쪽 근우 최소

    return dp[l][r][t];
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> T;
    while(T--)
    {
        cin >> N;
        memset(dp, -1, sizeof(dp)); //매초기화
        for(int i=0; i<N; i++) cin >> arr[i];
        cout << func(0, N-1, 0) <<"\n";
    }

    return 0;
}

 

평소 dp를 바텀업 방식으로 푸는 것을 선호하지만 탑다운 방식이 더 직관적일 때가 종종 있는 것 같아 연삼아 탑다운 방식으로 풀어보았다.

 

가장 왼쪽과 가장 오른쪽을 탐색해야 하므로 각 값을 재귀함수 func에 넣어준다.

그리고 현재 차례가 근우인지 명우인지 표시를 위한 변수로 하나 추가로 넣어준다.

해당 문제에서는 0을 근우 차례로, 1을 명우 차례로 잡았다.

 

이제 입력받은 t를 기준으로 근우 및 명우 차례에 대한 값을 따로 설정해준다.

먼저 t가 0 (근우 차례) 일 때 왼쪽과 오른쪽 중에서 최대값을 선택한다.

왼쪽을 골랐을 경우는 왼쪽 인덱스를 하나 증가시키고, r은 그대로, 그리고 t는 순서가 넘어가기에 1을 func에 넘겨준다.

반대로 오른쪽을 골랐을 경우는 오른쪽을 하나 감소시키고, l은 그대로, 마찬가지로 t는 순서가 넘어가기에 1을 넘겨준다.

그리고 각 선택한 값을 선택하여 더해준다.

 

명우 차례일 때도 비슷하다.

다만 여기서는 왼쪽인지 오른쪽인지 고른 값을 선택하여 더해줄 필요가 없다. (근우 것만 구해주면 됨)

추가로 다른 점은 최대를 구해줬던 근우 차례와 달리 여기선 최소를 구해준다.

왜냐하면 매턴 최선의 플레이를 한다고 가정했으므로 명우 기준으로 최대를 구해줘야 한다.

따라서 여기선 반대로 근우 기준 최소값을 구하기 위해 최소를 구별하여 저장해준다.

 

마지막으로 중복되는 계산을 방지하기 위해 현 dp값이 이미 존재한다면 바로 반환해주도록한다.