[BOJ] 1627번: 결투

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

무려 18번 만에 맞췄네요.. 쥬륵.. 맨 처음에는 i개의 빈 칸이 연달아있을 때 승리할 수 있는지 아닌지를 판단하고, 이를 이용해 DP로 어찌저찌 풀 수 있을 줄 알았습니다. 그런데 계속 오답이 발생하고 어디서 틀렸는지도 제대로 파악이 안되다가 결국 친구에게서 해답을 들었습니다. 바로 Grundy Number라는 것인데요, 지금의 문제와 같이 유한한 state가 존재하고 정보가 완전히 공개되어 차례로 수를 두는 게임에서는 NIM Game과 같은 원리를 사용할 수 있습니다. 검색해도 자료가 많이 없어서 조금 고생했습니다.

저는 3개를 연속해서 두면 이기는 게임으로 생각하는 대신, 2개를 한 칸 떨어지게 두거나 인접하게 두면 지는(P.P 혹은 PP) 게임으로 생각했고, G[i]를 점이 i개 연속해서 있을 때의 Grundy Number로 정의했습니다. 이 때

G[0] = 0, G[1] = 1, G[2] = 1, G[3] = 1, G[4] = 2, G[5] = 2, G[6] = 0이고, 그 이후로는 G[i]를 G[i-3],G[i-4],G[i-5], G[1]^G[i-6], G[2]^G[i-7],. .. 으로 계산할 수 있습니다. 이후 XOR이 0이면 LOSING, 0이 아니면 WINNING을 출력하고 WINNING일 경우 XOR이 0이 되도록 넘겨줄 수 있는 방법을 탐색했습니다.

이 문제로 하루를 날렸네요ㅎㅎ..

https://github.com/blisstoner/BOJ/blob/master/1627.cpp