BOJ-18937 "왕들의 외나무다리 돌게임" 풀기

문제 링크

이 문제는 자력솔을 못해서 남김

이 문제의 외나무다리 돌게임은 일종의 $N$개의 님 게임으로 치환 가능하다.

따라서 Sprague-Grundy Theorem에 의해서 각 외나무다리는 각각의 길이에서 2를 뺀 값의 돌을 가진 님 게임으로 치환이 가능하므로 각 (값 - 2)를 모두 xor 해준다음 0인지 판별하면 된다. $$\text{let};G = (A_1 - 2)\oplus (A_2 - 2) \oplus \cdots \oplus (A_n - 2)\\ \text{check flg =? 0}$$

왜냐하면 어떤 행동을 한 다음에는 $G$가 $0$인 경우에는 $G$는 $0$이 아닌 값으로 항상 바뀌고 $G$가 $0$이 아닌 경우에는 $0$으로 만들 수 있는 방법이 항상 존재한다. 그런데 행동을 할 수 없을때, 즉 패배했을 때에는 이 $G$ 값이 $0$이다. 따라서 만약 누군가의 차례일때 $G$값이 $0$이면 게임이 끝날을때에도 그 누군가는 $G$값이 $0$. 즉 항상 패배할 수 있다.

이 그런디 값을 이용해서 상태를 표현할 수 있다.