[게임 이론] - BOJ_11062 : 카드 게임

티스토리로 블로그를 이전한 뒤, 기념비적인 첫 글이다.
요즈음도 알고리즘을 공부하다보면, 금새 잊곤 하기 때문에 이렇게 하나 하나 글을 써보려 한다.
오늘 공부한 알고리즘은, 바로

"게임 이론"

알고리즘 분류만 보면 상당히 귀엽고 재밌어 보이지만, 상당히 악랄하다.

우선 오늘의 문제를 소개해보겠다.

boj 11062 - 카드 게임 GOLD III

처음 문제를 보았을 때는, 상당히 간단해 보인다.

그냥 항상 최선의 경우를 고르면 되는거 아님?

아니다

바로 다음과 같은 상황이 야기될 수 있다.

전체 게임 결과를 보았을 때, 최선의 선택을 해야하고, 상대 또한 최선의 선택을 하기에

내가 처음에 2를 뽑으면, 상대에게 5를 내주기 때문에 점수가 더 낮아지게 된다.

따라서 이 경우에서의 "최선의 수"란 다음과 같다.

물론 우리가 보기에는 , 그렇게 어렵지 않다. 하지만 컴퓨터가 어떻게 이 최선의 수를 미리 알 수 있을까?

바로 Top-down 방식의 dp로 해결할 수 있다.

💡문제 풀이 idea

먼저 각 카드의 값을, deck 배열에 저장한다.

이후, 내 차례 일때는, max( 왼쪽카드를 뽑고, 남은 게임의 경우의 수 , 오른쪽카드를 뽑고, 남은 게임의 경우의 수)

이런 방식으로 내 차례에서의 최선의 선택을 하게 된다.

따라서 점화식은 다음과 같다.

dp[left][right]=max(deck[left]+solve(left+1, right,0), deck[right]+solve(left, right-1,0));

하지만 상대 차례일 때는, 상대 또한 최선의 게임을 할 것이기 때문에, 나에게 최소한의 값을 전달해주어야 한다.

따라서 점화식은 다음과 같다.

dp[left][right]=min(solve(left, right - 1,1), solve(left + 1, right,1));

전체 코드를 작성해보면, 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

int t, n;
int deck[1010];
int score[1010];
int myscore;
int dp[1010][1010];
int solve(int left, int right,int turn);

int solve(int left, int right,int turn){
    if(left>right) return 0;

    if(turn==1){
        return dp[left][right]=max(deck[left]+solve(left+1, right,0), deck[right]+solve(left, right-1,0));
    }
    if(turn==0){
        return dp[left][right]=min(solve(left, right - 1,1), solve(left + 1, right,1));
    }
}

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

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

        cout<<solve(1, n, 1)<<'\n';
    }

    return 0;


}

내 턴과 상대턴을 구분해가며, 나는 나에게 있어 최선의 선택을, 상대는 나에게 있어 최악의 선택을 하고, 내가 선택한 카드들의 값만 return에 더해주며 내 점수를 계산하는 방식으로 코드를 짰다.

하지만 다음과 같은 코드는 시간초과를 받게 된다.

어째서?!

우리가 dp를 사용하는 이유가 무엇인가? 바로 재귀호출시에 이미 계산된 값을 재사용하여, 불필요한 계산을 안하게 하는 것이 아니던가?

따라서 다음 한 줄을 추가하게 되면 시간을 절약하여 무리 없이 통과할 수 있다.

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

는 틀렸습니다!

어째서?!

dp는 디버깅이 상당히 짜증난다. 재귀를 끝없이 들어가기 때문에.. 그래서 코드를 찬찬히 뜯어보다 문제점을 찾았다.

바로 tc가 여러개 주어지는 문제인데, dp 초기화를 안해주었던것! 하하.

fill(&dp[0][0], &dp[1010][1010], 0); 

따라서 fill로 dp초기화를 해주었다. fill로 이차원 배열을 초기화해줄때에는, 배열의 시작점과 끝점의 주소를 반환해주면 된다.
fill(&arr[0][0], &arr[ROW -1][COL], value) 바로 이런식으로. 나는 그냥 배열 전체를 초기화 해주었다.

 

드디어 accept! 

게임이론에 대해 더 공부해 보고 싶은 의욕이 드는 순간이 아닐 수 없다.

마지막으로 전체 코드를 남기며 글을 마치겠다.

#include <bits/stdc++.h>

using namespace std;

int t, n;
int deck[1010];
int score[1010];
int myscore;
int dp[1010][1010];
int solve(int left, int right,int turn);

int solve(int left, int right,int turn){
    if(left>right) return 0;

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

    if(turn==1){
        return dp[left][right]=max(deck[left]+solve(left+1, right,0), deck[right]+solve(left, right-1,0));
    }
    if(turn==0){
        return dp[left][right]=min(solve(left, right - 1,1), solve(left + 1, right,1));
    }
}

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

    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> deck[i];
        
        cout<<solve(1, n, 1)<<'\n';
        fill(&dp[0][0], &dp[1010][1010], 0); 
    }

    return 0;

    
}