[BOJ] 백준 11871번 : 님 게임 홀짝 (JAVA)

문제

koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. 

 

일반적인 님 게임과는 다르게 님 게임 홀짝은 돌을 제거할 때 규칙이 있다. 짝수 개수만큼 돌을 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거할 수 없다. 예를 들어, 한 돌 더미에 있는 돌의 개수가 8개인 경우에는 2, 4, 6개만 제거할 수 있다. (8개는 제거할 수 없다) 돌을 홀수 개수 만큼 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거해야한다. 예를 들어, 돌의 개수가 8개인 경우에는 홀수 개수 만큼 돌을 제거할 수 없으며, 돌의 개수가 7개인 경우에는 2, 4, 6, 7개만 제거할 수 있다.

 

각 돌 더미에 돌이 0개 또는 2개 남은 경우에는 더 이상 돌을 제거할 수 없으며, 모든 돌 더미에 돌이 0개 또는 2개 남은 경우에 게임이 끝난다. 이때, 마지막 돌을 제거하는 사람이 게임을 이긴다.

 

게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

 

 

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 2,147,000,000)가 주어진다. 모든 Pi가 2인 경우는 입력으로 주어지지 않는다.

 

 

출력

koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.

 

 

풀이

그런디 수를 이용하여 풀 수 있는 문제였습니다.

 

그런디 수를 잘 모르시는 분은 아래 포스팅에 있는 문제를 풀어보시거나, 최소한 그런디 수와 관련된 이론은 학습하시고 오시길 바랍니다.

 

 

[BOJ] 백준 16887번 : 핌버 (JAVA)

 

 

그런디 수를 구하기 위해서는 아래 식만 알고 있으면 됩니다.

 

 

문제에서 돌을 꺼낼 때, 짝수 돌은 짝수 개씩만 돌을 꺼낼 수 있고, 홀수 돌은 짝수 개씩 돌을 꺼내거나 전체 돌을 꺼낼 수 있다고 하였습니다.

 

따라서, 0과 2는 기저 사례이므로 그런디 수를 0으로 초기화한 다음, 1, 3, 4, ... 에 대하여 그런디 수를 차근 차근 구해보면 됩니다.

 

몇 가지 예시를 나열해 보면서 규칙성을 찾아봅시다.

 

돌이 1개일 경우, 다음 상태는 돌이 0개 밖에 없습니다.

0의 그런디 수는 0이므로 G₁ = 1 입니다.

 

돌이 3개일 경우, 다음 상태는 돌이 1개, 돌이 0개 입니다.

0의 그런디 수는 0, 1의 그런디 수는 1이므로 G₃ = 2 입니다.

 

돌이 4개일 경우, 다음 상태는 돌이 2개, 돌이 0개 입니다.

0의 그런디수는 0, 2의 그런디 수는 0이므로 G₄ = 4 입니다.

 

이를 나열하다보면, 홀수든 짝수든 관계없이 그런디 수가 1개씩 증가한다는 사실을 알 수 있습니다.

점화식으로 표현하면, 홀수는 (N + 1) / 2, 짝수는 (N - 1) / 2가 됩니다.

 

아래 소스코드를 통해 확인해 보시길 바랍니다.

 

 

소스코드

 

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