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

브루트포스로 풀면 당연히 시간초과가 날 것이다.

최악의 경우 O(2^n) 이고, n의 최댓값은 1000이므로 시간초과를 예상할 수 있다.

 

브루트포스의 과정을 생각해보면 같은 연산을 하게 되는 부분이 분명히 존재할 것이다.

예를 들어 [1, 2, 3, 4, 5, 6] 과 같이 카드가 있다고 가정해보자.

근우가 6, 5 를 가져가고 명우가 1, 2를 가져가는 경우든

근우가 6, 1 을 가져가고 명우가 5, 2를 가져가는 경우든

남아있는 카드는 [3, 4] 이다.

 

즉, 이전에 어떤 카드들이 선택되었든 남아있는 카드가 동일하다면 해당 카드들을 대상으로는 근우가 얻을 최대 점수는 항상 같을 것이다.

이를 이용해 dp를 활용하면 시간초과를 피할 수 있을 것이다.

 

나는 game() 이라는 함수를 정의해 dp배열을 채웠다.

dp[i][j]는 i번째 카드부터 j번째 카드가 남아있을 때 근우가 얻을 수 있는 최대 점수이다.

 

dp[i][j]가 0이 아니라면 한 번 계산된 경우이므로 추가적인 연산 필요없이 해당 값을 바로 참조하면 된다.

 

0이라면 한 번 계산해야 하는데

근우의 턴일 경우 dp값은 max(왼쪽 카드 + 왼쪽 카드를 제외한 경우에서의 최대 점수, 오른쪽 카드 + 오른쪽 카드를 제외한 경우에서의 최대 점수) 이다.

명우의 턴일 경우에는 dp값은 min(왼쪽 카드를 제외한 경우에서의 최대 점수, 오른쪽 카드를 제외한 경우에서의 최대 점수) 이다.

 

명우의 턴일 때가 잘 이해되지 않을 수 있다.

dp값은 다시 말하지만 "근우"가 얻을 수 있는 최대 점수이다.

명우의 턴일 때 명우 또한 최선의 전략으로 카드를 선택한다.

명우의 턴일 때 근우는 명우가 선택한 카드의 점수를 얻을 수 없고, 양 쪽 카드 중 제외한 경우에서의 최대 점수가 작은 쪽의 점수만을 얻을 수 있다.

 

 

---

정답 코드

#include <iostream>
#include <cstring>

using namespace std;

int T, N, card[1000], dp[1000][1000];

int game(int left, int right, int turn){
    
    if (left > right)
        return 0;
    if (dp[left][right] != 0)
        return dp[left][right];
    
    if (turn == 1)
        return dp[left][right] = max(card[left] + game(left + 1, right, 0), card[right] + game(left, right - 1, 0));
    else
        return dp[left][right] = min(game(left + 1, right, 1), game(left, right - 1, 1));
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> T;

    while (T--){
        cin >> N;
        for (int i = 0 ; i < N; i++)
            cin >> card[i];

        //dp
        game(0, N - 1, 1);

        //output
        cout << dp[0][N - 1] << "\n";

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