[Algorithm] 백준 11062 카드게임 풀이

21.11.14일 추가함.

 

문제를 보고 인공지능 시간에 배운 게임이론이라는 것을 알았다. min max 트리를 그려서 풀려고 했는데 역시 이론만 아는것이랑 실제 코드를 짜는것은 다르다는것을 느꼈다.. 그리고 재귀 호출시에 vector<int>를 복사해주었는데 이부분에서도 시간초과가 발생하였다. 

 

사소한 것이라 생각했지만 문제풀이에 크게 차이난다는 것을 느꼈다. 

 

이번 문제에서 알게된 것

• 재귀함수 호출시에 배열, 벡터 등의 값을 복사할 떄는 시간과 메모리 공간이 많이 소모되기 때문에 레페런스로 호출해주도록 한다. 
• 이론을 아는것과 구현은 다르다.
• min max 알고리즘(게임이론)에서 나를 기준으로 보고 상대의 점수가 min이 되도록 선택하도록 해야한다. 
• dp[left][right]는 내가 얻을 수 있는 점수이기 때문에 명우차례일때는 값을 더해주지않는다. 
• dp의 식을 생각해내는것은 어렵다. 배열을 모두 채우는데 사용하지않고 아이디어를 생각해내고 pruning하는데 사용한다. 
• 근우는 점수를 최대로 명우는 근우의 점수를 최소로 하기위해 게임을 진행해나간다.

---

코드

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

bool first = true;

int dp[1010][1010];

int gameTree(int left, int right, bool first, vector<int>& v)
{
    if(left > right) return 0;
    if(dp[left][right]) return dp[left][right];
    
    if(first == true)//근우일때.
    {
        int a = v[left] + gameTree(left + 1, right, false, v);
        int b = v[right] + gameTree(left, right - 1, false, v);
        
        return dp[left][right] = max(a, b);
    }
    else //명우 차례일 때.
    {
        int a = gameTree(left + 1, right, true, v);
        int b = gameTree(left, right - 1, true, v);
        
        return dp[left][right] = min(a,b);
    }
    
}
int main()
{
    int t;
    scanf("%d", &t);
    
    while(t--)
    {
        int n;
        scanf("%d", &n);
        
        vector<int> v;
        v.clear();
        for(int i = 0; i < n; i++)
        {
            int a;
            scanf("%d",&a);
            v.push_back(a);
        }
        
        int left = 0, right = n-1;
        gameTree(left, right, true, v);
        
        printf("%d\n",dp[left][right]);
        memset(dp, 0, sizeof(dp));
        
    }
}