BOJ 5386 - 금화 게임 (Python3)

게임 이론은 언제나 매우 힘들다. 근래 대회에서 게임 이론에 한 방 먹는 일이 계속 늘어가고 있다.

2023 연세대학교 프로그래밍 경진대회에서는 게임 이론 E를 건너뛰고 수학 F를 먼저 풀었고, 2024 MatKor w/s에서는 비록 다이아지만 게임 이론 한 문제를 못 풀어 2등과 3등이 갈렸다.

이게 연습으로 늘 만한 영역인지는 모르겠다. 잠 자기 전 랜디에서 보이는 게임 이론 문제가 튀어나와서 10분도 안 되어 바로 격파하긴 했지만 딱히 는 것 같지는 않다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

해적! 이는 멋진 직업인 것 같지만 큰 고충을 가지는 직업이다. 그 고충 중 하나는 많은 시간을 망망대해에서 지내야 한다는 점이다. 때때로 바람도 불지 않고, 하루종일 아무런 일도 없이 지나가는 날이 있을 수 있는 것이다. 너무 지루하기 때문에 해적들은 금화로 하는 여러 가지 놀이를 알고 있다. 그런 놀이 중 하나로 두 명의 해적이 하나의 금화 더미를 이용해서 하는 놀이가 있다. 이 놀이는 두 사람이 서로 차례를 번갈아 바꿔가면서 하는 놀이인데, 각 해적은 자기 차례에 어떤 주어진 정수 \(K\)가 주어질 때 \(K\)의 제곱수\((1, K, K^2,\cdots)\)만큼의 금화를 가져올 수 있다. 마지막 금화를 가져온 해적이 승리한다.

현재 금화 더미에 있는 금화의 개수와 \(K\)가 주어질 경우에 어떤 해적이 승리할까?

입력

첫 번째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며 두 개의 정수 \(S\)와 \(K\)로 이루어져 있다. \(1 \le S \le 10^9, 1 \le K \le 100\)을 만족한다. \(S\)는 금화의 개수를 의미하여 \(K\)는 각 차례에 \(1, K, K^2,\cdots\)개의 금화를 가져올 수 있다는 의미이다.

 

예제 입력)

# 예제 입력 1
5
5 1
3 2
8 2
50 3
100 10

 

출력

각 테스트 케이스 마다 한 줄에 처음 금화를 가져가는 해적이 이기기 위해 첫 번째 차례에 가져가야 하는 금화의 개수의 최솟값을 출력한다. 만약 처음 금화를 가져가는 해적이 어떤 개수의 금화를 가져가도 이길 수 없다면 0을 출력하면 된다.

 

예제 출력)

# 예제 출력 1
1
0
2
0
1

 

---

내 코드

def solve():
    N,K = map(int,input().split())
    if K%2 == 1: print(int(N%2 == 1)); return
    if N%(K+1) in (0,1,K): print(N%(K+1)); return
    else: print(int((N%(K+1))%2 == 1))
for _ in range(int(input())): solve()

 

우선 \(K\)가 홀수일 때는 무조건 매 턴마다 금화의 기우성이 바뀐다. 그러므로 전체 금화의 수가 홀수라면 무얼 집건 무조건 선수가 이기며, 아니라면 무조건 선수가 진다. 그렇다면 그냥 \(S\)를 2로 나눈 나머지만 출력해 주면 된다. 첫 번째 차례에 가져가야 하는 금화의 개수의 최솟값을 출력해야 하는데, 당연히 \(1, K, K^2, \cdots\)의 최솟값은 1이니까.

그렇지 않을 경우에는 금화를 가져가는 행위는 \(S\)를 \(K+1\)로 나눈 나머지를 1 키우거나, 1 줄인다는 사실을 캐치해야 한다. \(K^{2n}\equiv 1 \bmod K+1 \)이며, \(K^{2n+1}\equiv -1 \bmod K+1\)이기 때문이다.

따라서 \(S\)를 \(K+1\)로 나눈 나머지가 \(1, K\) 둘 중 하나면 정확히 그만큼만 가져와서 나머지를 0으로 만들어 주면 된다. 상대가 1 늘이면 나는 1 줄이면 되고, 반대로 상대가 1 줄이면 나는 1 늘이면 되니까. 만약 그렇지 않다면, 매 턴마다 \(S\bmod K+1\)의 기우성이 반드시 변한다는 사실을 캐치하자. 그러니 \(S\bmod K+1\)이 홀수면 무조건 선수가 이기며, 그렇지 않다면 무조건 후수가 이긴다. 자기 차례에 남은 금화의 수를 \(K+1\)로 나눈 나머지를 0으로 만들 수 있으니까. 0으로 만든다면 상대와 반대로 움직이면 항상 이길 수 있고.

남은 건 그대로 구현만 하면 된다. 여느 평범한 게임 이론이 그렇듯 구현은 증명보다 훨씬 간단하다.

 

이로서 5386번의 풀이를 마친다.