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

문제

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

 

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

 

 

입력

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

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

 

 

출력

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

 

 

풀이

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

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

 

 

필승 전략 게임

 

 

님 게임은 보통 마지막 돌을 가져간 사람이 이기는 규칙이지만, 이 문제는 마지막 돌을 가져간 사람이 지는 것이 핵심이었습니다.

 

이것과 관련된 내용이 문서에도 나와있는데, 아래 사진을 유심히 보시길 바랍니다.

 

 

 

 

 

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

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

 

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

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

 

하지만, 마지막 돌을 가져가는 사람이 패배하는 규칙인 경우, 조금 까다로워집니다.

돌이 1개인 더미가 존재하는지 판단하는 동시에, 돌이 1개인 더미가 홀수 개가 존재하는지 짝수 개가 존재하는지 판단하고, 님 합이 0인지 0이 아닌지 확인해야 합니다.

 

전반적인 로직은 아래와 같습니다.

 

 

1. 돌이 1개인 더미가 없을 경우, 님 합이 0이 아니면 선공, 0이면 후공이 승리한다.

 

2. 돌이 1개인 더미가 홀수 개일 경우, 님 합이 0이 아니면 선공, 0이면 후공이 승리한다.

 

3. 돌이 1개인 더미가 짝수 개일 경우, 돌이 1개가 아닌 임의의 더미를 돌이 1개인 더미로 만들고, 님 합이 0이 아니면 선공, 0이면 후공이 승리한다.

 

 

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

 

 

소스코드

 

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