[BOJ] 백준 11868번 : 님 게임 2 (JAVA)

문제

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

 

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

 

 

입력

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

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

 

 

출력

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

 

 

풀이

님 게임의 필승 전략을 활용한 문제입니다.

먼저, 이 전략에 대한 내용은 아래 문서를 통해 이해하실 수 있습니다.

 

 

필승 전략 게임

 

 

이 문제는 전형적인 님 게임의 규칙을 따르고 있습니다. 바로, 마지막에 돌을 가져간 사람이 이기는 것이죠.

문서를 읽다보면, 아래 사진과 같은 내용이 있습니다.

 

 

 

 

문서를 처음부터 읽으신 분은 아시겠지만, 여기서 '님 합'이라는 것은 돌 더미 각각의 돌 개수를 모두 XOR 연산을 한 값을 의미합니다.

가령, 돌 더미의 돌이 각각 1개, 2개, 3개가 있다면, 님 합은 1 XOR 2 XOR 3 XOR = 0 이 됩니다.

 

따라서, 마지막 돌을 가져가는 사람이 승리하는 규칙인 경우, 경기의 선공이 이기는지 후공이 이기는지 판단하는 것은 간단합니다.

님 합이 0이라면 후공이 승리하고, 님 합이 0이 아니라면 선공이 승리하는 것이죠.

 

이 문제는 마지막 돌을 가져가는 사람이 승리하는 규칙이므로 모든 돌 더미의 개수에 대하여 XOR 연산을 취한 다음, 0인지 0이 아닌지 판단하면 끝나는 문제입니다.

 

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

 

 

소스코드

 

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