[BOJ] 11717. Wall Making Game

문제 링크

$H \times W$ 크기의 보드판이 주어집니다. 두 명의 플레이어는 순서대로 다음 과정을 수행합니다.

1. 비어있는 칸을 하나 선택합니다. 해당 칸은 벽이거나 표시가 되어있으면 안되며 고를 수 있는 칸이 없으면 현재 턴의 플레이어는 패배합니다.
2. 선택한 칸을 포함하여 상하좌우 방향으로 벽을 설치합니다. 벽이 나오거나 보드를 벗어나기 직전까지 각 방향으로 벽을 설치해 나갑니다.

이 게임은 스프라그-그런디 정리를 사용할 수 있는 조건을 모두 만족합니다. 스프라그-그런디 정리를 활용해서 문제를 해결해 봅시다.

$grendy[sh][sw][eh][ew]$를 왼쪽 아래 칸이 $(sh, sw)$, 오른쪽 위 칸이 $(eh, ew)$가 되도록 보드판을 잘라 해당 보드판으로 게임을 할 때 그런디 수라고 정의하겠습니다.

그럼 다음 식을 만족합니다.

위 수식을 활용해서 $O(H^3W^3)$에 문제를 해결할 수 있습니다.