게임의 상태

우리가 PS에서 흔히 게임 이론 문제에서 나오는 게임들은 특이한 성질들을 가지고 있는 경우가 많다.

처음에, 각 성질들을 정리해보자.

순차적 게임(Sequential Game)

사람들이 순서에 맞게 차례대로 수를 두는 게임이다.

완전 정보 게임(Perfect information Game)

게임에 대한 모든 정보를 모든 참가자가 공유하는 게임이다.

포커는 상대방의 패를 모르기 때문에 완전 정보 게임이 아니다.

공정 게임(impartial game)

모든 참가자가 할 수 있는 행동이 동일한 게임이다.

체스 같은 경우, 누구는 검은색, 누구는 흰색 기물만 움직일 수 있기 때문에 공정 게임이 아니다.

노멀 게임(normal game)

자신이 취할 수 있는 행동이 아무것도 없을 때 지는 게임

예를 들어, 더 이상 ~ 할 수 없는 사람이 진다. 같은 게임이다.

미세르 게임(Misere game)

노멀 게임과 반대로 자신의 마지막 행동으로 할 수 있는 행동이 안남게 만들어야만 할 때 지는 게임

예를 들어, 마지막 ~ 를 하는 사람이 진다. 같은 게임이다.

노멀 님 게임

노멀 님 게임이란 $K$개의 성냥더미들에서 각각 턴을 돌아가며 어떤 하나의 성냥더미를 선택하여 그 더미에 남아있는 성냥들 중 원하는 수만큼 없앤 뒤, 더 이상 성냥을 가져갈 수 없는 사람이 지는 게임이다.

순차적 게임, 공정 게임, 노멀 게임, 완전 정보 게임의 성질을 띈다.

필승법

결론적으로 이 게임은 게임 초기 상태의 성냥더미들의 각 성냥들을 모두 $\oplus$ 한 값이 $0$이라면 선공이 지고, 아니라면 선공이 이긴다.

$\oplus$는 $xor$ 연산을 의미한다.

쌩뚱맞지만, 왜 이게 이렇게 되는지부터 알아보자.

일단 모든 성냥더미에 성냥이 없는 경우는 $0 \oplus 0 \oplus 0 \oplus \cdots \oplus 0=0$ 이다.

따라서 더 이상 가져갈 게 없는 상태가 모두 $\oplus$한 값이 0이라는 것이 보인다.

증명

현재 게임에서 모든 성냥더미를 $\oplus$한 값을 $S$라 하고, 행동을 취한 뒤의 값을 $T$라 하자.

성냥 더미는 모두 $K$개가 있고, $k$ 번 째의 성냥 더미의 성냥을 뺐다고 하자.

행동을 취하기 전 성냥들의 개수를 $x_1,~x_2,~\cdots x_K$ 라 하고, 행동을 취한 후에 성냥들의 개수를 $y_1,~y_2~\cdots y_K$ 라고 하자.

$$ \begin{aligned} T&=0\oplus T\\ &=S \oplus S \oplus T\\ &=S \oplus (x_1 \oplus x_2 \oplus \cdots \oplus x_K) \oplus (y_1 \oplus \cdots \oplus y_K)\\ &=S \oplus (x_1 \oplus y_1) \oplus \cdots \oplus (x_k \oplus y_k) \oplus \cdots \oplus (x_K \oplus y_K)\\ &=S \oplus (x_k \oplus y_k) ~~ \because ~~x_k \ne y_k\\ \end{aligned} $$

$\oplus$연산은 교환법칙과 결합법칙이 성립하기 때문에 위와 같은 결론이 나온다.

$T=S \oplus (x_k \oplus y_k)$ 라는 결론을 얻었다.

두 가지를 보자.

1. $S=0$ 이면 $T \ne 0$ 만 가능하다.

모든 성냥 더미에서 성냥이 하나도 안남아서 $S=0$인 경우는 제외하자. 그 경우는 이미 게임이 끝난 상태이기 때문에 고려를 해줄 필요 없다.

$T=S \oplus (x_k \oplus y_k)=x_k \oplus y_k$ 가 되고 $x_k \ne y_k$ 이기 때문에 $T \ne 0$이다.

$\because 0 \oplus a = a$

2. $S \ne 0$이면 T=0으로 만들 수 있다.

$S$를 이진수로 표현하면 $S=1xxxx_{(2)}$ 라고 해보자.

어떤 성냥 더미는 $10000_{(2)}$ 이상의 성냥 개수가 남아있다는 뜻이다.

이 성냥더미의 성냥 개수를 $1yyyy_{(2)}$ 라고 한다.

$1xxxx_{(2)} \oplus 1yyyy_{(2)}=0zzzz_{(2)}$ 가 되고, 때문에 항상 $1yyyy_{(2)}-0zzzz_{(2)}$ 개의 성냥을 더미에서 빼버리면 $T=0$ 을 만들 수 있다. $\square$

$1yyyy$개가 있는 성냥 더미에서 $1yyyy-0zzzz$개의 성냥들을 취할수 있다는 것은 자명하다.

연습 문제

BOJ 11868 - 님 게임 2 를 이제 풀 수 있다.

모든 수를 $\oplus$해서 결론을 내주면 된다!

void solve() {  
   int n;  
   cin >> n;  
   int a = 0;  
   for (int i = 0, j; i < n; i++) {  
      cin >> j;  
      a ^= j;  
   }  
   if(a == 0) cout << "cubelover";  
   else cout << "koosaga";  
}

미세르 님 게임

미세르 님 게임은 노멀 님 게임과 반대로 마지막 남은 성냥을 가져가는 사람이 진다.

필승법

미세르 님 게임은 특이하게 고려해줘야 할 케이스가 하나 있다.

바로 성냥이 $2$개 이상인 더미가 하나도 없는 경우인데, 이 때는 항상 한 개씩만 제거할 수 있으므로 성냥 더미가 짝수일 때만 선공이 이긴다.

그 외의 상황에서의 필승법은 크게 다르지 않다. 상대방에게 $S$를 항상 $0$을 줄 수 있다면 승리한다.

$S=$모든 성냥들의 $\oplus$들의 결과

내가 $S$가 $0$이 아닌 값을 받고 남은 성냥 더미는 두 개밖에 없다고 하자.

이를 $a, b ~~ (a \ne b, a, b > 0)$ 라고 하고, $2, b$ 를 만들어서 상대에게 준다. 그러면 상대는 아무것도 못하고 지게 된다.

두 개가 모두 $1$ 인 경우는 $a=b$ 인 경우이므로 불가능하고 $1, 2$ 같은 경우도 결국 $1, 1$을 상대에게 만든다면 이기기 때문에 모든 경우에서 이길 수 있다.

연습 문제

BOJ 11694 - 님 게임

원래 원조 님 게임은 미세르 님 게임이라고 한다. 위 문제를 풀어보자.

void solve() {  
   int n, x = 0;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   for (int i: a) x ^= i;  
   int ge_than_2 = 0;  
   for (int i = 0; i < n; i++) if (a[i] >= 2) ge_than_2 = 1;  
   if (!ge_than_2) {  
      if (n % 2 == 0) cout << "koosaga";  
      else cout << "cubelover";  
   } else {  
      if (!x) cout << "cubelover";  
      else cout << "koosaga";  
   }  
}

근데 이 문제 어쩌다가 난이도가 플레티넘 2로 올라갔지?

노멀 님 게임과 그런디 수(Grundy Number), 님버(Nimber)

노멀 님 게임으로 다시 돌아와보자.

근데, 성냥 더미가 단 1개일 경우를 고려해보자.

그러면 처음에 성냥 더미가 $0$개인 경우에만 선공이 지고 항상 선공이 이길 수 있다.

다 가져버리면 끝이니까…

님버(Nimber)

새로운 개념을 정의해보자.

성냥 더미가 한 개인 님 게임에서 그 성냥 더미의 성냥 개수를 님버(Nimber) 라고 하자.

노멀 님 게임을 생각해보면, 위의 결론들로 인해 성냥 더미가 몇 개가 있든 연쇄적인 $\oplus$연산의 결과로 게임에 대한 하나의 님버를 얻을 수 있다.

그리고, 이 님버가 $0$이면 선공이 지고 그렇지 않으면 선공이 이긴다는 것을 알 수 있었다.

성냥 더미가 여러개이면, 각 성냥더미들은 성냥 개수만큼 님버를 가지며, 각 님버들을 모두 $\oplus$ 한 값이 모든 성냥 더미를 봤을 때의 최종 님버이다.

그런디 수(Grundy Number)

님 게임에서는 결국 님버가 $0$이나 아니냐만 중요할 뿐이다.

후술할 스프라그-그런디 정리에 의하면 성질(순차적, 완전 정보, 공정, 노멀)을 만족하는 게임들의 상태를 모두 이 님버로 표현할 수 있다.

모든 게임이 성냥을 가지고 하는건 아니기 때문에 게임의 상태들을 바로 이 님버로 표현한 수들을 바로 그런디 수(Grundy Number)라고 한다.

그러니까 어떻게 보면 그런디 수는 결국 다른 게임에서의 님버이므로 비슷한 의미를 지닌다.

행동집합 예제 - 돌 게임

행동집합은 현재 게임 상태로부터 어떤 행동을 했을 때 다음 게임의 상태들의 집합을 의미한다.

행동집합 얘기를 하며 님 게임이 아닌 다른 게임에서의 그런디 수를 활용하는 방법을 알아보자.

우리가 살펴볼 것은 돌 게임이다.

돌 게임은 $N$개의 돌을 차례대로 몇 개씩 가져가서 마지막 돌을 가져가는 사람이 이기는 노멀 게임이다.

이 문제는 굉장히 유명하고 스프라그 그런디 정리 관련 글에서 빠짐없이 찾아볼 수 있을 정도로 좋은 예시이므로 시간이 난다면 백준에서 돌 게임 $1 \to 8$ 까지 모두 풀어보도록 하자.

BOJ 9655 - 돌 게임 은 가져갈 수 있는 수가 $1~ or ~ 3$ 개 뿐인 문제이다.

처음에 돌이 아무것도 없을 때는 행동 집합이 공집합일 것이다. 이는 님버 $\star0$와 같다.

$$ \{\}=\star0 $$

돌이 하나도 없는 상태와, 노멀 님 게임에서 성냥이 하나도 안 남아있을 때의 상태를 동일하게 생각하겠다는 뜻이다.

돌이 1개가 있을 때의 행동 집합은 돌을 1개를 가져가는 것 뿐이다.

$$ \star1=\{\star0\} $$

행동 집합은 현재 게임 상태에서 취할 수 있는 행동의 결과의 집합이므로, 돌이 $0$개 남은 상태가 행동 집합의 유일한 원소가 된다.

돌이 한 개 있는 상태는 노멀 님 게임에서 성냥이 한 개 있는 경우와 동일하게 보게 되었으므로, 돌이 한 개가 있으면 선공이 이긴다.

이제 계속해서 보자.

$$ \begin{aligned} \star0&=\{\}\\ \star1&=\{\star0\}\\ \star2&=\{\star1\}=\{\{\star0\}\}=\{\}=\star0\\ \star3&=\{\star0,\star2\}=\{\star0\}=\star1\\ \star4&=\{\star1,\star3\}=\{\star1\}=\cdots=\star0\\ \star5&=\{\star2,\star4\}=\{\star0\}=\star1\\ \vdots\\ \end{aligned} $$

이 행동 집합들이 계속해서 이전에 얻은 결과를 기반으로 결국 $\star0$과 $\star1$로 귀결되는 것을 볼 수 있다.

이러한 특징상 스프라그-그런디 정리의 문제들은 일반적인 DP문제를 푸는 것 과 흡사하게 풀린다.

어쨌든 규칙적으로 봤을 때 짝수면 항상 $\star N=\star0$ 이고 홀수면 $\star N=\star1$ 이기 때문에 홀수일 때만 선공이 이긴다는 것을 알 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   if (n & 1) cout << "SK";  
   else cout << "CY";  
}

그런디 수를 계산하는 규칙 ⭐️

그런데 저 규칙은 왜 나타나는 것일까? 매우 큰 수에서는 저 규칙이 통하지 않을 수도 있지 않을까?

결론부터 말하자면 항상 통한다. 항상 현재 게임 상태의 그런디 수를 알 수 있고, 그 그런디 수를 이용해 선공이 이길지 질지 알 수 있기 때문이다.

그런디 수를 계산하는 규칙은 다음과 같다.

1- 게임을 더 이상 진행할 수 없는 상태의 그런디 수는 항상 $0$ 이다.

님 게임에서 성냥이 하나도 없는 상태라고 볼 수 있다. 님버=0 이다.

2- 행동 집합의 그런디 수들의 Mex 연산이 바로 현재 게임 상태의 그런디 수이다.

이는 스프라그 그런디 정리 자체이며 뒤에 더 자세히 다룬다.

Mex는 음이 아닌 정수 중 집합 내에 없는 가장 작은 수를 의미한다.
Mex$(\{0,1,3\})=2$ 이다.

3- 게임이 여러개이거나 행동으로 인해 게임이 여러개로 나뉜다면, 그 게임들의 $\oplus$ 연산의 합이 해당 상태의 그런디 수이다.

님 게임의 예시를 통해 이를 증명했다.

N, P position과 행동집합 정리들

스프라그-그런디 정리를 알아보기 전에, $N$ 포지션과 $P$ 포지션과 정리들에 대해 알아보자.

N, P position

어떤 게임이 순차적, 완전 정보, 공정 게임이라면 항상 어떤 게임의 현재 상태는 $N$ 행동집합이거나 $P$ 행동집합으로 표현된다.

  • N position(행동집합) - 지금 수를 두는 사람이 항상 이기는 상태
  • P position(행동집합) - 지금 수를 두는 사람이 항상 지는 상태

물론 모든 플레이어가 최선을 다해 플레이를 할 때를 가정한다.

행동집합의 정의에 의해 어떤 행동집합은 $\{N, P, N, P, \cdots \}$ 처럼 구성이 되어 있을 것이다.

만약 이 행동집합 내에 $P$ 포지션이 하나라도 있으면, 현재의 상태는 $N$ 행동집합이다.

왜냐면 다음 상태를 $P$ 를 만드는 행동을 해서 상대방을 항상 지게만들 수 있기 때문이다.

반대로 $P$ 포지션이 하나도 행동집합에 없다면 현재 상태는 $P$ 포지션이다.

행동집합의 합

두 행동집합의 합은 다음과 같이 표현된다.

$$ \begin{aligned} G_1&=\{A,B,C\}\\ G_2&=\{D,E\}\\ \\ G_1+G_2&=\{G_1+D,G_1+E\} \cup \{A+G_2,B+G_2,C+G_2\} \end{aligned} $$

즉, 두 행동집합이 합쳐진 결과는 원래 할 수 있었던 행동들에서 다른 원래 행동집합들이 합쳐진 것의 합집합이다.

성냥 더미가 2개인 님 게임을 생각해보면, 첫 번째 성냥 더미에서 성냥을 가져가면 두 번째 성냥 더미의 성냥 개수는 그대로이고 반대도 동일하게 동작하기 때문임을 알 수 있다.

행동집합의 합은 교환법칙과 결합법칙이 모두 성립한다.

행동 집합의 등가성 (Equivalence)

두 행동집합 $G,G’$가 어떤 다른 행동집합 $H$와 합친 결과인 $G+H$와 $G’+H$가 항상 같은 $N, P$ 포지션이 나온다면 $G$와 $G’$는 Equivalence 하다고 하고 $G \approx G’$ 처럼 표현한다.

Lemma 1

어떤 $P$ 포지션의 행동 집합 $A$에 대해 $G \approx G+A$

증명

행동 집합의 등가성을 보이기 위해 어떤 행동 집합 $H$에 대해 $G+H$와 $G+A+H$가 있다고 하자.

1- $G+H$ 가 P 포지션일 때

$G+H$ 에서 행동을 하면 상대방도 $G+H$ 에서 하고 내가 $A$에서 행동을 하면 상대방도 $A$에서 하면 결국 마지막에는 $P$ 포지션이 되어 성립한다.

2- $G+H$ 가 N 포지션일 때

$G+H$ 의 행동집합엔 $P$ 포지션이 있고, 그걸 고른다면 다음 게임의 상태는 $P$ 포지션의 상태에 $A$ 를 더한 것이 된다.

하지만 이전의 결론으로 $P$ 포지션을 $P$ 에 더해도 $P$ 가 됨이 보여졌기 때문에 $A+G+H$ 는 $N$ 포지션에 있음이 보인다.

결론적으로 $G+H$가 $N$이든 $P$든 항상 $P$를 더하면 동일한 포지션이 유지되기 때문에 $G \approx G + A$ 이다. $\square$

Lemma 2

$G \approx G' \Longleftrightarrow G+G' \text{ is } P \text{ position}$

증명

등가성에 의해 $G \approx G’$ 이므로 $G+G$와 $G+G’$ 는 동일한 포지션을 갖고, $G+G$ 가 $P$ 포지션임을 보이면 $G+G’$ 도 $P$ 포지션이여야 한다.

$G+G$ 를 보기 쉽게 $G_1+G_2~(G_1=G_2)$ 라고 하자.

$G_1$ 에서 행동을 하면 상대방도 $G_1$ 에서 행동을 하고, $G_2$ 에서 행동을 하면 상대방도 $G_2$ 에서 행동을 하면 수가 바닥나는건 선공이기 때문에 $G+G$는 $P$ 포지션이다.

따라서 $G+G’$ 도 $P$ 포지션이다.

역으로, $G+G’$ 가 $P$ 포지션이라고 하자.

Lemma 1에 의해 $G \approx G+G+G’$ 이고 결합법칙을 적용해 $G \approx (G+G)+G’$ 가 되고 동일한 행동집합의 합은 $P$ 포지션임을 앞서 보였으므로 다시 Lemma 1에 의해

$$ G\approx (G+G)+G'\approx P+G' \approx G' $$

$\square$

스프라그 그런디 정리

모든 노멀, 공정 게임은 하나의 성냥더미를 가진 님 게임으로 환원된다.

구체적으로, 주어진 게임의 상태는 행동 집합내에 그런디 수들의 Mex이다.

증명

구조적 귀납법을 사용한다.

행동 집합 $G$가 다음과 같다고 가정할 때,

$$ G=\{G_1,G_2,\dots,G_k\} $$

귀납가정에 의해 각 $G_i$는 모두 그런디 수로 환원된다.

$G_i \to \star n_i$ 라 하자.

다음과 같이 그런디 수로만 이루어진 행동 집합 $G’$ 를 정의한다.

$$ G'=\{\star n_1,\star n_2,\dots,\star n_k\} $$

${\color{salmon} G \approx G’}$ 임을 보이자.

$G+G’$ 라는 행동 집합이 있다고 하자.

내가 $G$에서 $G_i$ 를 고르면 상대방은 $G’$ 에서 $\star n_i$ 를 고른다.

내가 $G’$ 에서 $\star n_i$ 를 고르면 상대방이 $G$에서 $G_i$ 를 고른다.

따라서 $G+G’$ 는 $P$ 포지션이며 Lemma 2에 의해 $G \approx G’$ 이다.

$G’$ 내의 그런디 수 중 Mex를 $m$ 이라고 하자.

${\color{salmon} G’ \approx \star m}$ 임을 보이자.

이는 동일하게 $G’+\star m$이 $P$ 포지션임을 보이는 것으로 충분하다.

by Lemma 2

선공이 $\star m$에서 $\star m’~(m’<m)$ 를 고른다고 하자.

후공이 $G’$ 에서 $\star n_i~~(n_i=m’)$ 인 $\star n_i$ 를 고르면 $\star m’+ \star m’$ 인 상태가 되고 당연하게 $\star m’ \approx \star m’$ 이므로 $\star m’+\star m’$는 $P$ 포지션이라 선공이 지므로 $G’+\star m$은 $P$ 포지션이다.

$\star m’+ \star m’$ 가 된 이유는 선공이 $\star n_i$ 를 골랐고 이는 $\star m’$ 이기 때문이다.

선공이 $G’$에서 $\star n_i~(n_i<m)$ 를 고른다고 하자.

마찬가지로 후공이 $\star m$ 에서 $\star m’~(n_i=m)$ 인 $\star m’$ 를 고르면 $\star n_i+\star n_i$ 가 되어서 $P$ 포지션이다.

선공이 $G’$ 에서 $\star n_j~ (n_j>m)$ 를 고른다고 하자.

그럼 상대방에게 $\star n_j+\star m$ 을 넘겨주게 되고, $\star n_j$ 는 귀납 가정에 의해 행동집합에 $\star m$을 포함하므로 상대방은 나에게 $\star m+\star m$을 넘겨주면 이는 $P$ 포지션이여서 내가 지게된다.


결국 모든 경우에 $G’+\star m$은 $P$ 포지션이며 이는 Lemma 2에 의해 $G’ \approx \star m$을 의미한다.

그리고 $G \approx G’ \approx \star m$ 이기 때문에 증명이 완료된다. $\blacksquare$

연습 문제들

기본적인 문제들은 두 가지 유형으로 나뉜다.

  1. 바로 $\oplus$ 을 통해 그런디 수를 구할 수 있는 경우
  2. 행동집합에 어떤 그런디 수들이 있는지 보고 직접 Mex연산을 이용해 그런디 수를 구해야 하는 경우

돌 게임 같은 친구들은 2번의 예시이고, 기본 님 게임 문제들은 1번의 예시이다.

돌 게임

BOJ 9655 - 돌 게임, BOJ 9655 - 돌 게임 5

아까 바로 그 문제이다.

BOJ 9656 - 돌 게임 2

미세르 돌 게임이다.

미세르 게임에선 공집합을 $\star1$ 로 정의하고 하나가 남은 상황을 $\star0$ 으로 정의해줄 수 있다.

$$ \begin{aligned} 0 \Rightarrow \{\}=\star1\\ 1 \Rightarrow \star 0\\ 2 \Rightarrow \{\star1\}=\{\}=\star1\\ \vdots \end{aligned} $$

따라서 이것도 그냥 홀짝 문제이다.

BOJ 9657 - 돌 게임 3, BOJ 9660 - 돌 게임 6

$$ \begin{aligned} 0 &\Rightarrow \star0\\ 1 &\Rightarrow \{\star0\}=\star1 ~~~~ \because \text{Mex}(\{\star0\})=1\\ 2 &\Rightarrow \{\star1\}=\star0\\ 3 &\Rightarrow \{\star0,\star0\}=\star1\\ 4 &\Rightarrow \{\star1,\star1,\star0\}=\star2\\ 5 &\Rightarrow \{\star2,\star0,\star1\}=\star3\\ 6 &\Rightarrow \{\star3,\star1,\star0\}=\star2\\ \vdots \end{aligned} $$

이렇게 규칙이 나오고, 7로 나눈 나머지가 0이나 2일 때만 선공이 진다는 것을 알 수 있다.

님 게임

BOJ 16895 - 님 게임 2, BOJ 16895 - 님 게임 3

노멀 님 게임이다 $\oplus$ 만 열심히 하자.

BOJ 11694 - 님 게임

미세르 님 게임이다. 위에 풀이를 참고한다.

BOJ ​11871 - 님 게임 홀짝

BOJ 16877 - 핌버

다른 게임

BOJ 13034 - 다각형 게임

우리가 그런디 수의 규칙을 바로바로 찾지 못하는 경우가 있다.

그런디 수들의 합 연산은 $\oplus$ 연산과 같았기 때문에,

다각형을 나눌 수 있는 모든 경우의 수대로 나누어보고 두 나뉘어진 게임판의 그런디 수를 $\oplus$ 한 값들을 모두 배열에 저장해두고 거기서 Mex를 찾으면 해당 $N$각형에 대한 그런디 수가 나온다.

재귀 DP식으로 그런디 수를 구할 수 있다.

int grundy[1025];
int fn(int n) {
   if (n <= 1) return 0;
   if (n == 2 || n == 3) return 1;
   int &ret = grundy[n];
   if (~ret) return ret;

   vi tmp;
   tmp.pb(fn(n - 2));
   int l = 1, r = n - 3;
   for (int i = 2; i <= n - 2; i++) {
      tmp.pb(fn(l) ^ fn(r));
      l++;
      r--;
   }
   uniq(tmp);
   for (int i = 0;; i++)
      if (tmp[i] != i) {
         ret = i;
         break;
      }

   return ret;
}
void solve() {
   memset(grundy, -1, sizeof grundy);
   int n;
   cin >> n;
   if (fn(n)) cout << 1;
   else cout << 2;
}

BOJ 3596 - 크로스와 크로스

$g(n)=$ $n$ 길이 보드에서의 그런디 수 라고 하자. 그리고 $g(i)=0,\,i \le 0$ 이다.

$N$ 길이 보드의 행동집합 $G(N)$ 은 다음과 같다.

$$ G(N)=\{g(-2) \oplus g(N-3),g(-1) \oplus g(N-2),\cdots\} $$

왜냐면 어떤 칸에 x 표시를 한다는 것은 좌우 인접한 두 칸들을 못쓰게 만들어버린다는 뜻이기 때문이다.

이제 저 행동집합내부의 그런디 수들의 Mex가 결국 $G(N)$ 이고 $O(N^2)$에 구할 수 있다.

int n, dp[2001];  
int fn(int i) {  
   if (i <= 0) return 0;  
   if (i < 3) return 1;  
  
   int &ret = dp[i];  
   if (~ret) return ret;  
  
   vi nim;  
   for (int j = 1; j <= i; j++) {  
      int L = j - 3;  
      int R = i - j - 2;  
      nim.pb(fn(L) ^ fn(R));  
   }  
   uniq(nim);  
   for (int i = 0;; i++) if (nim[i] != i) return ret = i;  
}  
  
void solve() {  
   memset(dp, -1, sizeof dp);  
   cin >> n;  
   cout << (fn(n) == 0 ? 2 : 1);  
  
   for (int i = 1; i <= 2000; i++) {  
      if (fn(i) == 0) debug(i);  
   }  
}

BOJ 16881 - 행렬 게임

님 게임과 비슷해보이지만 생각이 필요한 문제이다.

각 행마다의 그런디 수만 구하면 모두 $\oplus$하면 되므로 하나의 행에 대해서만 생각하자.

만약 $m=1$이라면 숫자가 그런디 수 그 자체이다.

$m=2$ 일 때는, 우리가 그 다음 숫자의 그런디 수를 알고 있으므로

$dp[i][g]=$현재 $i$개가 있고 다음 더미의 그런디 수가 $g$ 일 때 현재 그런디 수 라고 정의하자.

이는 $O(N^2)$ DP로 구할 수 있고 문제를 해결할 수 있다.

Solution 2

하지만 이렇게 직접 그런디 수를 DP로 구하지 않고 더 간단히 구할 수 있다.

오른쪽의 그런디 수가 $g$이고 현재 수가 $i$라고 하자.

$i$ 에서 긱 수를 뺄 때 행동의 행동이 모두 합쳐지면 어떤 행동 집합이 나오는지 살펴보자.

$g \ne 0$ 이라고 하자.

모두 뺄 때는 할 수 있는 행동이 바로 $\star g$가 된다.

$$ G=\{\star g\}=\star0 $$

하나만 남기고 뺄 때도 행동이 하나로 강제된다. 하나를 빼게 되면 다음 행동 집합이 ${\star g}$ 가 되어 결국 $\star1$ 이 된다.

$$ G=\{\{\star g\}\}=\{\star 0\}=\star1 $$

두 개만 남기고 뺄 때는 할 수 있는 행동이 2개이다. 한 개만 빼거나 모두(2개) 뺄 수 있다.

$$ G=\{\star1,\star g\}=\star0 $$

세 개만 남기고 뺀다면($i-3$ 개를 뺀다면)

$$ G=\{\star0, \star1, \star g\}=\star2 ~~~ \text{if }g \ne 2 $$

이다. 그런데 여기서 $g < i$ 이고 $g=2$ 라고 하자. 그럼 위의 식이

$$ G=\{\star0, \star1, \star g\}=\star3 ~~~ \text{if }g = 2 $$

처럼 되고 어떤 과정에서 그런디 수가 원래 들어가야 할 수보다 $1$ 증가된다.

또한 $\star g$ 는 그 빈 자리의 수이므로 Mex 연산에서 항상 그 자리가 빌 일이 없다.

따라서 마지막에

$$ G=\{\star(i-2),\star(i-3),\cdots,\star1, \star0, \star g\}=\star(i-1) $$

처럼 되어야 할 것이

$$ G=\{\star(i-1),\star(i-2),\cdots,\star1, \star0, \star g\}=\star i $$

처럼 되어도 문제가 없다는 뜻이다.

따라서

$$ dp[i][g]= \begin{cases} i & \text{if } ~ g < i \\ i-1 & \text{if } ~g \ge i \end{cases} $$

라는 결론이 나온다.

여전히 $O(N^2)$ 이지만, 꼭 그런디 수에 대한 Mex 연산을 직접 구현할 필요 없이 논리적인 사고를 통해 그런디 수를 찾는 방법을 최적화 할 수 있다는 점에서 이 문제를 주의깊게 볼 필요가 있다.

Comments

You may also enjoy

Web Element Event

Event를 처리함에 있어 stopPropagation, preventDefault에 대해 알아보자.