[BOJ] 백준 16889번 : 중복 없는 님 게임 (JAVA)

문제

구사과와 큐브러버가 님 게임을 하려고 한다. 님 게임은 돌 더미 N개를 이용하며, i번째 돌 더미에 있는 돌의 개수는 Ai개이다. 두 사람은 턴을 번걸아 가지면서, 게임을 진행한다. 각 턴은 돌 더미를 하나 고르고, 그 돌 더미에서 돌을 1개 이상 제거하는 것으로 이루어져 있다.

 

게임은 구사과가 먼저 시작한고, 자신의 턴이 돌아왔을 때 돌을 제거할 수 없는 사람이 게임을 진다.

 

이 게임은 너무 많이 했기 때문에, 오늘은 새로운 규칙을 하나 추가해서 하려고 한다.

 

새로 추가한 규칙은 한 돌 더미에서 같은 개수의 돌을 또 제거할 수 없다는 것이다. 예를 들어, 한 돌 더미에서 돌을 4개 가져갔으면, 이후에는 그 돌 더미에서 돌을 4개 가져갈 수는 없다. 이 규칙은 두 사람에게 모두 적용되고, 돌 더미마다 독립적으로 적용된다. 

 

두 사람이 게임을 최적의 방법으로 했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 106)이 주어진다. 둘째 줄에는 돌 더미에 있는 돌의 개수 A1, A2, .., AN(1 ≤ Ai ≤ 60)이 주어진다.

 

 

출력

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

 

 

풀이

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

 

다음 상태를 정의하여 그런디 수를 구하는 방법만 알고 있으면, 크게 어렵지 않은 문제였습니다.

N = 0 부터 사례를 나열해 봅시다.

 

 

N = 0 일 때는 기저 사례이므로 G₀ = 0 입니다.

 

N = 1 일 때는 다음 상태가 돌이 0개 밖에 없습니다. 따라서 G₁ = 1 입니다.

 

N = 2 일 때는 다음 상태가 돌이 0, 1개 입니다. G₀ = 0 이지만, 여기서 G₁은 1이 아닙니다. 이미 돌을 1개 꺼냈으면, 그 다음 번에 다시 1개를 꺼낼 수 없으므로 G₁ = 0이 됩니다. 결과적으로, G₂ = 1 이 됩니다.

 

N = 3 일 때는 다음 상태가 돌이 0개, 1개, 2개 입니다. 앞의 2개의 상태는 제약 없는 님 게임이므로 G₀ = 0 이고, G₁ = 1 입니다. 하지만, 돌이 2개인 상태는 돌을 2개만 빼낼 수 있으므로, G₂ = 1이 됩니다. 따라서, G₃ = 2가 됩니다.

 

위와 같은 방식으로 돌을 빼낼 수 있는 제약 조건을 잘 고려하면서 그런디 수를 나열하면, 다음과 같은 규칙이 보입니다.

 

 

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, ...

 

 

같은 그런디 수가 2개, 3개, 4개, ... 순으로 증가하는 규칙입니다. 이제, 위의 패턴을 알게 되었으니 코드로만 잘 짜면 됩니다.

 

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

 

 

소스코드

 

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