[BOJ] 백준 16887번 : 루트 님 게임 (JAVA)

문제

구사과와 큐브러버가 루트 님 게임을 하려고 한다. 님 게임은 돌 더미 N개를 이용하고, i번째 돌 더미에는 Ai개의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 게임을 진행한다. 각 사람의 턴이 되면, 다음을 해야 한다.

 

• 돌 더미 하나를 고른다. 이 때, 그 돌 더미에 있는 돌의 수를 x라고 한다.
• 0 ≤ y < x, x^1_/4 ≤ y ≤ x^1_/2를 만족하는 정수 y를 고르고, 고른 돌 더미에 있는 돌의 개수를 y로 바꾼다.

 

더 이상 턴을 진행할 수 없는 사람이 게임에서 진다.

 

돌 더미의 개수 N과 각 돌 더미에 포함된 돌의 개수가 주어졌을 때, 누가 이기는지 구하는 프로그램을 작성하시오. 두 사람은 최적의 방법으로 게임을 진행하고, 구사과부터 턴을 갖는다.

 

 

입력

첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 둘째 줄에 돌 더미에 포함된 돌의 개수 Ai(1 ≤ Ai ≤ 1,000,000,000,000)가 주어진다.

 

 

출력

구사과가 게임을 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

 

 

풀이

스프라그-그런디 정리를 이용하여 풀 수 있는 문제였습니다.

 

아마, 이 포스팅을 찾아오신 분들은 위 이론을 몰라서 오신 것은 아닐겁니다. 킹리적 갓심을 가지고 "특정 수" 이후로는 값이 변하지 않겠지라는 생각으로 제출했다가 틀리신 분들일 듯합니다..

 

그런디 수를 관찰하기 위해서 적당히 10^8까지 넣어보면, 아래와 같은 그런디 수 변화 양상을 보입니다.

 

 

 

 

제곱 수이거나 (제곱 수 + 1) 부분에서 그런디 수가 변화한다는 사실을 알 수 있습니다. 그리고 50626 부터 10^8까지는 그대로 1이라서 더 이상 변화하지 않는 것처럼 보였습니다.

 

여기서 단순히 그런디 수를 1 ~ 3 까지는 0, 4 ~ 16 까지는 1, ... , 50626 ~ 10^13 까지는 1로 판단하고 제출하면 틀립니다.

 

분명, 50626 ~ 10^13 사이에서 변하는 구간이 있다는 의미인데, 무턱대고 처음부터 10^13 까지는 돌려볼 수는 없는 노릇이었죠.

 

그래서 일단 10^13 일 때의 그런디 수라도 관찰하기 위해서, 코드를 돌려보니까 2가 나왔습니다.

네.. 50626 에서 10^13 사이에 변하는 구간이 있었다는 의미죠.

 

저는 일단 50626 부터 10^8까지는 그런디 수가 1임을 확인했기때문에 10^8 ~ 10^13 중에 그런디 수가 2로 변하는 지점을 찾기로 하였습니다.

 

사실, 여기서도 변하는 지점이 여러 개일 수 있는데.. 기도 메타로 1개만 있다고 가정하였습니다.

위의 10^8 ~ 10^13 사이를 이분탐색을 취하여 처음으로 2로 바뀌는 지점을 찾았고, 그 값은 2562991876 였습니다.

 

그래서 50626 ~ 2562991875 까지는 그런디 수를 1, 2562991876 ~ 10^13 까지는 그런디 수를 2로 판단하고 코드를 제출하니까 맞았습니다.

 

여담으로, 2562991876은 50626을 제곱한 수와 같았습니다. solved.ac에 난이도 측정 답변을 보면, 어떤 분이 사실 손으로도 풀 수 있는 문제라고 하는데... 이렇게 기도 메타 외에 정석적인 풀이가 무엇인지 궁금합니다.

 

 

소스코드

 

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