[백준 3032] 승리

문제

www.acmicpc.net/problem/3032

 

알고리즘

DP

 

풀이

선영이와 정인이가 게임을 합니다. 번갈아 숫자를 골라가며 고른 수의 인접한 수를 고를 때, 선영이가 이길 수 있는 경우를 세는 문제입니다.

 

인접한 수를 골라나가며 범위를 좁히는 것에서 DP를 떠올릴 수 있습니다. 

 

$solve(l,r,t)$= $l, r$부터 범위를 골라나갈 때, 선영이 차례에서 얻을 수 있는 최대 점수 ($t$가 짝수일 때 선영이 차례)

 

정인이의 차례($t$가 홀수일 때)에는 최악의 플레이를, 선영이의 차례에서는 최선의 플레이를 하면 선영이가 최대한 이길 수 있게 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, ans, sum;
int arr[100];
int cache[100][100];

int solve(int l, int r, int turn) {
    if (turn == N)
        return 0;
    int& ret = cache[l][r];
    if (~ret)
        return ret;

    int nl = (l == 0 ? N - 1 : l - 1);
    int nr = (r == N - 1 ? 0 : r + 1);

    if (turn % 2 == 1) {
        ret = min(solve(nl, r, turn + 1), solve(l, nr, turn + 1));
    } else {
        ret = max(solve(nl, r, turn + 1) + arr[nl], solve(l, nr, turn + 1) + arr[nr]);
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    memset(cache, -1, sizeof(cache));
    cin >> N;
    rep(i, N) {
        cin >> arr[i];
        arr[i] &= 1;
        sum += arr[i];
    }

    rep(i, N) {
        if (solve(i, i, 1) + arr[i] > sum / 2)
            ans += 1;
    }
    cout << ans;
    return 0;
}