BOJ 16876 - 재미있는 숫자 게임

BOJ 16876 - 재미있는 숫자 게임

$dp[i][j]$ 를 현재 숫자 $i$ 이고 $j$ 번 두었을 때 현재 사람의 입장에서 지금이 N-Position 이라면 $1$ 아니라면 $0$이라고 정의한다.

이는 $m$의 기우성과 관련이 있는데, $m$ 턴을 해서 $N$보다 숫자가 커졌을 때 구사과가 이긴 것이고, $m$이 짝수라면 마지막 턴($m$턴 이후)는 구사과의 턴이므로 이긴 것이라서 $1$ 그렇지 않다면 $0$ 이 된다.

이런식으로 $dp[i][m]$ 에 대해 모두 전처리 해두고 DP를 재귀적으로 수행하면 누가 이기는지 알 수 있다.

int dp[10001][101];
int p10[5]{1, 10, 100, 1000, 10000};
void solve() {
   memset(dp, -1, sizeof dp);
   int n, m;
   cin >> n >> m;

   for (int i = 0; i <= 9999; i++) {
      dp[i][m] = i > n ? (m % 2 == 0 ? 1 : 0) : (m % 2 == 0 ? 0 : 1);
   }
   function<int(int, int)> fn = [&](int i, int j) -> int {
      int &ret = dp[i][j];
      if (~ret) return ret;
      ret = 0;

      int any_lose = 0;
      for (int k = 0; k < 4; k++) {
         int c = i / p10[k] % 10;
         int nc = i - c * p10[k] + md(10, c + 1) * p10[k];
         if (!fn(nc, j + 1)) any_lose = 1;
      }

      return ret = (any_lose ? 1 : 0);
   };
   cout << (fn(n, 0) ? "koosaga" : "cubelover");
}