BOJ 3032 승리

* BOJ 3032 승리

[분류 - 다이나믹 프로그래밍]

  원형 다이나믹을 많이 풀어봤다면 비교적 쉽게 느껴질 문제입니다.

[풀이]

  1. 1부터 N까지 각각을 첫 번째 수로 보고 진행한다.

  2. 고를 수 있는 수가 최대 두 개가 되는데, 이 때 어떤 것을 골라야 필승인지를 검사하는 로직을 추가한다. 즉, 상대가 무조건 지는 경우가 있는지 탐색한다.

  현재 골라야하는 플레이어는 골라야하는 수의 구간으로 알 수 있으며 그 때까지 선영이가 선택한 홀수의 개수를 저장해두었다가 모든 수를 다 사용했을 때, 누가 승리하는지 판단하도록 구성해주면 된다.

dp[l][r][c] = 선영이가 c개의 홀수를 얻었고, 현재 플레이어는 l번째 수 또는 r번째 수를 선택할 수 있을 때의 승리 가능성

#include<cstdio>
#include<cstring>
const int MAX_N = 100;
int N, tot, dp[MAX_N][MAX_N][51], A[MAX_N];
int rec(int l, int r, int c) {
    l = (l + N) % N, r %= N;
    int turn = !((l < r ? r - l - 1 : r + N - 1 - l) % 2);
    if (l == r) {
        c += turn * A[l];
        int oc = tot - c;        
        return turn ? c > oc : c <= oc;
    }
    int& ret = dp[l][r][c];
    if (ret != -1) return ret;
    return ret = !rec(l - 1, r, c + turn * A[l]) || !rec(l, r + 1, c + turn * A[r]);
}
int main() {
    memset(dp, -1, sizeof dp);
    int ans = 0, i;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        A[i] %= 2;
        tot += A[i];
    }
    if (N == 1) ans = A[0];
    else {
        for (i = 0; i < N; i++)
            ans += !rec(i - 1, i + 1, A[i]);
    }
    printf("%d", ans);
    return 0;
}