백준 11062 카드 게임 혼내주기

 

작년에 교내 SW육목경진대회에 나가면서 minimax 알고리즘과 alpha beta pruning 알고리즘을 공부했었는데, minimax 알고리즘으로 푸는 문제였다.
근우의 차례에는 값이 최대가 되도록, 명우의 차례에는 값이 최소(명우의 최선의 플레이)가 되도록 구현하면 된다.

 

교내 대회를 나간 경험이 ps에서 도움이 된다니... 이런 경험이 공부하면서 즐거운 시간들 중 하나인 것 같다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int arr[1000], cache[1000][1000];
int n;

void input() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
}

int d(int from, int to, bool turn) {

    int& ret = cache[from][to];
    if(ret != -1) return ret;

    if(from == to) {
        if(!turn) return ret = arr[from];
        else return ret = 0;
    }

    if(!turn) ret = max(d(from+1, to, !turn) + arr[from], d(from, to-1, !turn) + arr[to]);
    else ret = min(d(from+1, to, !turn), d(from, to-1, !turn));
    
    return ret;
}

int main() {
    fastio;
    int t; cin >> t;

    while(t--) {
        input();
        memset(cache, -1, sizeof(cache));
        cout << d(0, n-1, 0) << "\n";
    }
}