[BOJ] 백준 18937번 : 왕들의 외나무다리 돌게임 (JAVA)

문제

흰 왕(Whiteking)과 검은 왕(Blackking)이 외나무다리 돌게임을 하려고 한다.

 

이 게임에서는 N개의 외나무다리를 사용한다. i번째 외나무다리는 일렬로 나열된 Ai개의 칸으로 이루어져 있다. 모든 외나무다리의 첫 번째 칸에는 흰 돌을 올려놓고, 마지막 칸에는 검은 돌을 올려놓고 게임을 시작한다.

 

각 턴에 왕은 자신의 색깔의 돌 중 하나를 이동시켜야만 한다. 이동시킬 때는 같은 다리의 다른 칸으로 돌을 움직여야 하며, 상대방의 돌을 뛰어넘거나, 같은 칸으로 이동할 수 없다. 이 조건을 어기지 않는 한, 자신의 돌을 두 돌이 멀어지는 방향으로 움직여도 된다. 번갈아 가면서 턴을 진행하며, 자신의 차례에 아무 돌도 움직일 수 없는 왕이 패배한다. 둘 다 최적의 방법으로 게임을 할 때, 누가 이길지 예측해보자!

 

 

입력

첫째 줄에는 외나무다리의 개수 N이 주어진다.  

둘째 줄에는 각 외나무다리의 칸 수 A1, A2, A3, ..., AN이 주어진다.

셋째 줄에는 먼저 시작하는 왕의 이름이 주어진다. 

 

 

출력

첫째 줄에 이길 왕의 이름을 출력한다. 이름은 항상 첫글자가 대문자임에 유의하여라.

 

 

풀이

스프라그-그런디 정리를 이용하여 풀 수 있는 문제였습니다. 외나무 다리의 칸 수가 2일 때부터, 쭉 나열하면서 규칙성을 파악해 봅시다.

 

외나무 다리의 칸 수가 2일 때는, 선공이 무조건 패배하므로 G₂ = 0 입니다.

외나무 다리의 칸 수가 3일 때는, 한 칸 움직일 수 있으므로 다음 상태는 칸 수가 2일 떄와 같습니다. 따라서 G₃ = 1 입니다.

외나무 다리의 칸 수가 4일 때는, 한 칸 또는 두 칸 움직일 수 있으므로 다음 상태는 칸수가 2일 때와 3일 때와 같습니다. 따라서 G₄ = 2 입니다.

이 쯤에서 눈치채셨겠지만, G_n = n - 2와 같습니다.

 

여기서, 저는 앞으로 가는 경우만 고려했지, 뒤로 가는 경우는 고려하지 않았습니다.

하지만, 뒤로 가는 경우는 의미가 없습니다. 만약, 어떤 플레이어가 돌을 뒤로 움직였다면, 반대쪽 플레이어도 돌을 뒤로 움직이면 그만이기때문이죠.

 

이제, 규칙성을 파악하였으니, 주어지는 외나무 다리의 칸의 그런디 수에 대해 XOR 합을 구하면 됩니다.

아래 소스코드를 통해 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.