BOJ 11867 박스 나누기 게임

사용한 알고리즘

알고리즘 설명

일반적인 DP 문제이다
DP state는 두 박스에 돌상태로 DP[A_BOX][B_BOX] 로 정한다
여기서 A_BOX를 고르는 경우, B_BOX를 골라서 나누는 경우중 상대방이 지는 경우가 한번 이라도 있으면 이길 수 있다.
이러한 상태를 DP로 저장하고 dfs로 모두 탐색한다.

풀이

// baekjoon 11867 yechan
#include <bits/stdc++.h>
using namespace std;

const int MAX_N=101;

int N;
int dp[MAX_N][MAX_N];

int dfs(int A, int B) {
    // win condition
    if (A == 2 || B == 2)
        return 1;

    int &ret = dp[A][B];
    if (ret != -1) return ret;

    ret = 0;
    // Choose first Box
    for (int i=1; i<A; i++)
        ret |= !(dfs(i, A-i));
    // Choose Second Box
    for (int i=1; i<B; i++)
        ret |= !(dfs(i, B-i));

    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    int A, B;
    scanf("%d%d", &A, &B);
    int ret = dfs(A, B);
    puts(ret == 1 ? "A":"B");
    return 0;
}