BOJ 14430 자원 캐기

사용한 알고리즘

알고리즘 설명

일반적인 DP 문제이다
DP state를 DP[N][M] 으로 잡는다
DP[x][y]를 (1,1)에서 (x,y)까지 올때 캘수 있는 최대 자원수로 정의
오른쪽과 아래쪽 방향으로만 갈 수 있기 때문에, (x,y)로 가는 경의에 수는 (x-1, y)와 (x, y-1)에서 출발하는 경우이다
두 경우 중 자원 수가 가장 많은 경우를 채택한다.

풀이

// 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;
}