문제

박스 나누기 게임은 두 박스를 이용해서 하는 게임이다.

처음에 한 박스에는 돌이 N개, 다른 박스에는 돌이 M개 들어있다. 두 사람은 턴을 번갈아가면서 게임을 진행한다.

각 사람은 박스를 하나 선택하고, 박스안에 들어있는 돌을 모두 비운다. 그 다음, 다른 박스에 들어있는 돌을 적절히 두 박스로 분배한다. 이때, 두 박스에는 돌이 적어도 1개 이상 있어야 한다.

두 박스에 돌을 각각 1개씩 만드는 사람이 게임을 이기게 된다.

N과 M이 주어진다. 두 사람이 게임을 완벽하게 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100, N과 M이 모두 1인 경우는 없다)

출력

게임을 먼저 시작한 사람이 게임을 이기면 A를, 그 다음에 시작한 사람이 게임을 이기면 B를 출력한다.

예제 입력

1 2

예제 출력

A

내가 했던 풀이 방법

1. dp를 -1로 초기화해준다. 여기서 -1은 아직 계산되지 않았음을 의미한다.
2. N과 M 중 더 큰 값이 오른쪽에 오도록 한다. 즉, N이 M보다 항상 작아야 한다. (계산을 편하게 하기 위함)
3. recursion에서는 x, y 값이 0 또는 x가 y보다 클 때 0을 return 한다. (해당 내용은 문제에서 가정한 내용과 일치하지 않은 경우이다.) x와 y가 모두 1일 때 승리하는 상황임으로 따로 처리해준다. 만약 dp[x][y]가 -1이 아닐 때는 이미 계산된 내용이므로, 연산 수를 줄이기 위해 해당 값을 return 해준다. 일단 dp[x][y]를 0으로 저장해준다. 그리고 x와 y에 대해서 돌을 나눠준다. 해당 경우를 recursion 해주었을 때 값이 0 또는 2인 경우가 한 번이라도 존재한다면, A가 승리한다. 해당 경우가 없을 경우는 B가 승리한다. (해당 경우를 recursion 해주게 되면 내가 나눠준 결과로 다음에 상대방이 진다는 걸 의미하므로, 본인은 승리하게 되는 것이다.)
4. recursion이 모두 끝난 결과가 1일 때 A가 승리하고 아닐 때는 B가 승리한다.

코드

const fs = require('fs');
let input = fs.readFileSync(0, 'utf-8').toString().trim().split(' ').map(Number);

let N = input[0];
let M = input[1];

let dp = Array.from({ length: 101 }, () => Array(101).fill(-1));

if (N > M) {
  [N, M] = [M, N];
}

function recursion(x, y) {
  if (x === 0 || y === 0 || x > y) {
    return 0;
  }

  if (x === 1 && y === 1) {
    return 2;
  }

  if (dp[x][y] !== -1) {
    return dp[x][y];
  }

  dp[x][y] = 0;

  for (let i = 1; i <= Math.floor(y / 2); i++) {
    let temp = recursion(i, y - i);

    if (temp === 0 || temp === 2) {
      return (dp[x][y] = 1);
    }
  }

  for (let i = 1; i <= Math.floor(x / 2); i++) {
    let temp = recursion(i, x - i);

    if (temp === 0 || temp === 2) {
      return (dp[x][y] = 1);
    }
  }

  return dp[x][y];
}

console.log(recursion(N, M) === 1 ? 'A' : 'B');

회고

게임 이론 문제는 해당 결과가 승리했으니 나는 패배한다. 이런 경우가 너무 많아서 뇌가 꼬이는 것 같아. 게임 이론 문제...싫어...