[Algorithm]Baekjoon 11062번 : 카드 게임

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

11062번: 카드 게임

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, n;
int cardScores[1001] = { 0 };
int dp[1001][1001][2] = { 0 };
int prefixSum[1001] = { 0 };
 
int DFS(int startIndex, int endIndex, bool turn)
{
    if (startIndex == endIndex) return cardScores[startIndex];
    if (dp[startIndex][endIndex][turn] != 0) return dp[startIndex][endIndex][turn];
 
    int curSum = prefixSum[endIndex] - prefixSum[startIndex - 1];
    int selectLeft = curSum - DFS(startIndex + 1, endIndex, !turn);
    int selectRight = curSum - DFS(startIndex, endIndex - 1, !turn);
 
    return dp[startIndex][endIndex][turn] = max(selectLeft, selectRight);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
 
        cin >> n;
 
        for (int i = 1; i <= n; ++i)
        {
            cin >> cardScores[i];
 
            prefixSum[i] = prefixSum[i - 1] + cardScores[i];
        }
 
        cout << DFS(1, n, true) << endl;
    }
}

 

각자 양끝에 있는 카드를 순서대로 한개씩 고르는 게임을 한다.

근우먼저 시작하는데, 상대인 명우가 최선을 다했을 때 근우가 얻을 수 있는 카드누적값을 구하는 문제이다.

그저 최대값을 구하는게 아닌, '상대가 최선을 다했을 때' 근우가 얻을 수 있는 최대값이다.

 

상대가 최선을 다했을 때의 값을 구해야하니, 특정구간과 누구 턴인지 매개변수로 주어지면 해당턴의 상대가 최선을 다했을 때의 최대값을 리턴해주는 DFS함수를 정의해보자.

 

위 코드 DFS함수에서 세번째 매개변수가 true이면 근우턴이고, false이면 명우턴이다.

즉, DFS(1,n,true) 이면 현재 1 ~ n의 카드리스트이면서 근우턴일 때, 상대인 명우가 최선을 다했을 때의 근우의 최대값을 리턴한다.

만약 DFS(3,6,false)이면, 3~6의 카드리스트이면서 명우턴일 때, 상대인 근우가 최선을 다했을 때 명우의 최대값을 리턴한다.

 

필요한 값이 무엇인지 판단했고, 해당값을 구하기위한 DFS함수를 일단 정의했다. (내용물은 아직 구현안했지만)

가만히 보아하니, 특정구간에서의 특정턴에 대한 계산이 중복될거란걸 눈치챌 수 있다. (이정도 눈치는 챙겨야한다)

그러니 DP테이블을 아래와같이 정의해보자.

 

int dp[1001][1001][2];

== dp [startIndex] [endIndex] [turn] 

 

이제 DFS함수의 내용을 구현해줘야 한다.

이 함수의 목적은 '현재 주어진 구간에서', '현재 턴의 상대편이 최선을 다했을 때', '현재 턴의 사람이 얻을 수 있는 최대 카드값'을 리턴하는 것이다.

현재턴인사람이 왼쪽,혹은 오른쪽을 선택한다면 선택하고 남은 나머지구간에 대해서 DFS를 진행하게 됐을 때 남은 나머지구간에서의 상대턴의 최대값이 나올 것이다.

이 때, '현재 구간의 총 카드누적값 - 상대턴의 최대값' == '현재구간'에서, 상대가 최선을 다했을 때 내 최대값

 

왼쪽, 오른쪽을 뽑아야하니 두 경우에 대해 값을 구한 후, 더 큰값을 리턴해주면 되는것이다. (30, 31번째 라인)

자 여기서 주의해야할 것은, '현재 구간의 총 카드누적값'이다.

매번 구간의 크기만큼의 반복문을 돌려서 누적값을 계산하면 시간이 오래걸릴 것이다.

 

그렇기때문에 prefixSum을 이용한다.

미리 각 인덱스까지의 누적값을 저장해놨다가, 특정구간의 누적값이 필요할 때 prefixSum[endIndex] - prefixSum[startIndex-1] 을 하면 한번의 계산으로 startIndex ~ endIndex구간의 누적값을 바로 계산할 수 있다.