[BOJ] 백준 11872번 : 님 게임 나누기 (JAVA)

문제

koosaga와 cubelover가 "님 게임 나누기 버전"을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 다음과 같이 2가지 중 하나를 선택할 수 있다.

 

1. 일반적인 님 게임과 똑같이 돌 더미 하나를 선택해 돌을 하나 이상 제거한다.
2. 돌이 적어도 2개 있는 돌 더미 하나를 선택한 다음, 두 개의 비어있지 않은 돌 더미로 나눈다. (돌은 제거할 수 없다)

 

전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. 

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

 

 

입력

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

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 2×109)가 주어진다.

 

 

출력

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

 

 

풀이

님 게임의 필승 전략과 그런디 수를 이용하여 풀 수 있는 문제였습니다.

아직, 그런디 수가 무엇인지 모르시는 분은 아래 포스팅을 꼭 읽고 오셔야 합니다.

 

 

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

 

 

그런디 수를 정의하는 방법만 알면 규칙성을 찾아서 쉽게 풀 수 있었습니다.

 

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

돌이 1개일 때는 다음 상태가 돌이 0개 밖에 없으므로 G₁ = 1 입니다.

 

돌이 2개일 때는 다음 상태가 돌이 0개, 1개, 그리고 돌을 (1개, 1개) 로 쪼개는 경우가 있습니다.

돌을 쪼개지 않는 경우의 그런디 수는 0, 1 이고, 돌을 쪼개는 경우의 그런디 수는 1 ^ 1 = 0 입니다.

따라서, G₂ = 2 입니다.

 

돌이 3개일 때는 다음 상태가 0개, 1개, 2개, 그리고 돌을 (1개, 2개) 로 쪼개는 경우가 있습니다.

돌을 쪼개지 않는 경우의 그런디 수는 0, 1, 2 이고, 돌을 쪼개는 경우의 그런디 수는 1 ^ 2 = 4입니다.

따라서, G₃ = 4 입니다.

 

돌이 4개일 때는 다음 상태가 0개, 1개, 2개, 3개, 그리고 돌을 (1개, 3개), (2개, 2개) 로 쪼개는 경우가 있습니다.

돌을 쪼개지 않는 경우의 그런디 수는 0, 1, 2, 4이고, 돌을 쪼개는 경우의 그런디 수는 1^4 = 5와 2^2 = 0 입니다.

따라서, G₄ = 3 입니다.

 

이를 나열하다보면, 그런디 수가 0, 1, 2, 4, 3, 5, 6, 8, 7, ... 이 됩니다.

0을 제외하고 이를 4개씩 분리해 보면,

 

1 2 4 3

5 6 8 7

9 10 12 11

...

 

과 같이 4를 나눈 나머지가 3일 때는 원래 수보다 1 증가하고, 나머지가 0일 때는 원래 수보다 1이 감소하는 규칙성을 띄고 있습니다.

(여기서, 원래 수라는 의미는 "1 2 3 4 5 6 7 8 ... " 과 같이 순차적으로 1씩 증가할 때의 수를 뜻합니다.)

 

이제, 그런디 수의 규칙성을 파악하였고, 식으로도 나타낼 수 있게 되었습니다.

마지막으로, 입력 받은 돌 더미의 그런디 수를 파악하여 XOR 합을 구한 뒤, 선공이 이기는지 후공이 이기는지 판단하면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

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