[Python] 7787번 빨간 칩, 초록 칩

 

 

https://www.acmicpc.net/problem/7787

7787번: 빨간 칩, 초록 칩

---

 

22/11/10

 

 

스프라그-그런디 정리를 이용해서 풀 수 있는 문제로, 규칙을 찾아서 쉽게 풀 수 있다.

 

근데 증명하는건 굉장히 어렵다... 증명하는 과정을 한번 살펴보자.

---

 

문제 접근 방식:

 

 

그런디 수를 구하는 방법으로 그런디 수를 계속 재귀적으로 20개까지 구하다 보면 아래와 같은 규칙을 발견할 수 있다.

(20개까지의 그런디 수는 알아서 구해보자)

 

만약 칩 개수를 2로 나누었을 때, 나머지가 1이면 그런디 수가 1이다.

 

만약 칩 개수를 4로 나누었을 때, 나머지가 2이면 그런디 수가 2이다.

 

만약 칩 개수를 8로 나누었을 때, 나머지가 4이면 그런디 수가 3이다.

 

이를 반복하자면, 다음과 같은 규칙을 발견할 수 있는데,

 

만약 칩 개수를 $2^{i}$로 나누었을 때, 나머지가 $2^{i-1}$라면 그런디 수가 $i$이다.

 

이를 다른 말로 적자면 다음과 같다.

 

만약 칩 개수가 $N$이라고 하고, $N = k*2^{i} + 2^{i-1} = 2^{i-1}(2k+1) = 2^{i-1}\times m$($m$은 홀수)이라면, 그런디 수가 $i$이다.

 

근데 이게 왜 그런지 증명하는 것은 조금 까다로운데, 기존에 나와있는 규칙을 한번 다시 증명해보는 것이 우리의 목적이므로, 수학적 귀납법으로 증명해보자.

 

명제 1)
어떤 임의의 자연수 $N$은 항상 $2^k \times m$,($m$은 홀수)꼴로 유일하게 표현이 된다.

명제 1의 증명)

표현성)
만약 $N$이 홀수일 경우를 상정해보자.
$N$이 홀수라면, $k = 0$으로 잡으면 $N = m$($m$은 홀수)을 만족시키므로, 표현 가능하다.
만약 $N$이 짝수라고 해보자.
그렇다면, $N$을 소인수 분해 한다면, $2$를 항상 포함하고 있으므로, 그 모든 $2$들을 묶는다면 홀수 소인수들만 남게 된다. 이들을 모두 곱해도 홀수이므로, $2^{k} \times m$꼴로 표현 가능하다.
유일성)
유일하지 않다고 가정해보자.
그렇다면, 어떤 $k \neq k'$과 $m \neq m'$($m'$은 홀수)가 존재하여, $N = 2^{k'} \times m'$을 만족시킨다.
이때, $N = 2^{k'} \times m' = 2^k \times m$이므로, $ 2^{k'} \times m' - 2^k \times m = 0$이다.
일반성을 잃지 않고, $k < k'$이라고 하면, $2^k ( 2^{k''}\times m' - m ) = 0$로 인수분해 할 수 있다. (단, $k + k'' = k'$)
이때, $2^k$는 절대 $0$이 될 수 없다.
따라서, $( 2^{k''}\times m' - m ) = 0$이 되야 하는데, $2^{k''}\times m'$은 짝수이고, $m$은 홀수 이기 때문에 모순이 생긴다.
따라서 증명 완료.

본 증명)
명제 2)
$N = 2^{i}\times m$($m$은 홀수)이라면, 그런디 수가 $i+1$이다.

수학적 귀납법을 활용하자.
모든 $0 \leq n \leq i-1$에 대해 저 명제가 성립한다고 가정하자.

명제 1에 의해, 어떤 자연수 $N$을 $2^{i} \times m$,($m$은 홀수)꼴로 항상 유일하게 표현할 수 있다.
따라서 가정또한 자연스럽게 성립이 된다.(전제에서 그런디 수가 잘 정의됨)
이 수에서 $N$의 약수 하나를 뺀 수, $N'$을 생각해보자.

$N$의 약수에는 위의 표현식에 의해, $1, 2, ..., 2^{i-1}$이 들어가 있다.

만약 $N$에 $1$을 뺀다고 하면, $1 = 2^0 \times 1$이므로, $N' = N-1 = 2^i \times m - 2^0 \times 1 = 2^0(2^i \times m -1)$이다.
따라서, 가정에 의해 이때의 그런디 수는 $1$이다.

마찬가지로, $N$에 $2^k$ (단, $1 \leq k \leq i-1$)을 뺀다고 하면, $N' = 2^i \times m - 2^k \times 1 = 2^k(2^{i-k} \times m -1)$ 이므로, 가정에 의해 이때의 그런디 수는 $k$이다.
$N$의 약수에는 자기 자신도 있으므로, 자기 자신을 빼면, $0$이므로 이때의 그런디 수는 $0$이다.

하지만, 우리는 $N$에서 $N$의 약수 하나 $D$를 뺌으로써 $N' = 2^{i} \times m$,($m$은 홀수)꼴로 표현할 수 없다.
만약 만들 수 있다고 가정한다면, 뺀 약수 $D$도 $2^i \times m'$, ($m'$은 홀수)꼴이어야 저렇게 표현 할 수 있고, 그렇다면 $N' = N - D = 2^i \times m - 2^i \times m' = 2^i \times (m - m')$이고, $m - m'$은 짝수이므로, $N' = 2^{i} \times m$,($m$은 홀수)꼴이 아니게 된다.

따라서, 어떤 약수 $D$를 빼서 나올 수 있는 그런디 수 $g$는 $0 \leq g \leq i$이므로, 이 그런디 수들에 $mex$함수를 취해주면, $i+1$이 나오게 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 7787번 빨간 칩, 초록 칩
# 게임 이론, 스프라그-그런디 정리
'''
접근 방법:
규칙 찾기
'''
r, g = map(int, input().split())
for i in range(30):
    remain_r = r % (2**(i+1))
    remain_g = g % (2**(i+1))
    if 2**i == remain_r and 2**i == remain_g:
        print('B player wins')
        break
    elif 2**i == remain_r or 2**i == remain_g:
        print('A player wins')
        break
    else:
        continue