[백준 9661] 돌 게임7

문제

게임이론을 활용한 문제이다. 게임이론은 DP와 같이 묶이는 경우가 많은데, 이 문제는 수학적인 관찰을 활용해 풀 수 있다.

9661번: 돌 게임 7

DP로 풀 경우

$DP[0] = CY$ 이고, 나머지 $N$들을 채울 때 SK의 첫 선택에 따라 DP로 풀이가 가능하다.

$N-4^x \geq 0$ 이고 $DP[N-4^x] = CY$ 인 경우가
하나 이상 있다면 $DP[N] = SK$,
하나도 없다면 $DP[N] = CY$가 된다.

이 때 시간복잡도는 $O(NlogN)$ 이다.
$N$의 최댓값이 $10^{12}$ 이므로 이렇게 풀어서는 시간 초과가 발생한다.

수학적 풀이

$4^x\equiv1,(mod,5)$ 또는 $4^x\equiv4,(mod,5)$ $(x\geq0)$라는 사실을 통해 $O(1)$만에 풀이가 가능하다.
이로 도출할 수 있는 내용은, 중간 과정에서 누군가가 남은 돌이 5로 나누어 떨어지도록 돌을 가져가면 그 사람이 필승이다.

1) $N\equiv0,(mod,5)$일 경우
SK가 어떻게 돌을 가져가든 CY는 남은 돌의 개수를 5로 나누어 떨어지게 가져갈 수 있다.
-> CY 필승

2) $N\equiv1,(mod,5)$ 또는 $N\equiv4,(mod,5)$일 경우
SK가 처음부터 남은 돌의 개수를 5로 나누어 떨어지게 가져갈 수 있다.
-> SK 필승

3) $N\equiv2,(mod,5)$ 일 경우
3-1) SK가 남은 돌의 $mod,5$가 1이 되게 돌을 가져가면, CY가 남은 돌의 개수를 5로 떨어지게 가져갈 수 있다.
3-2) SK가 남은 돌의 $mod,5$가 3이 되게 돌을 가져가면 CY가 남은 돌의 $mod,5$가 2가 되게 가져갈 것이고, 이것이 반복되어 $N=2$ 인 상태로 SK 순서가 될 것이다.
-> CY 필승

4) $N\equiv3,(mod,5)$ 일 경우
4-1) SK가 남은 돌의 $mod,5$가 4가 되게 돌을 가져가면, CY가 남은 돌의 개수를 5로 떨어지게 가져갈 수 있다.
4-2) SK가 남은 돌의 $mod,5$가 2가 되게 돌을 가져가면 3)에 의해 SK가 승리한다.
-> SK 필승

정답

N을 5로 나눈 나머지가
0, 2이면 CY
1, 3, 5이면 SK를 출력한다.