[BOJ] 백준 11869번 : 님블 (JAVA)

문제

님블은 1×N 직사각형에서 즐기는 게임이다. 직사각형은 1×1 크기의 정사각형으로 나누어져 있고, 가장 왼쪽 정사각형은 0번, 그 오른쪽 정사각형은 1번, ..., 가장 오른쪽 정사각형은 N-1번이다. 각 정사각형에는 동전이 놓여져 있을 수 있는데, 한 개 이상 놓여져 있을 수도 있다.

 

두 사람은 턴을 번갈아가면서 게임을 진행한다. 턴은 동전을 하나 고르고, 동전을 왼쪽으로 한 칸 이상 옮기는 것으로 이루어져 있다. 

 

모든 동전이 0에 있으면 게임이 끝나게 되며, 마지막 동전을 0으로 옮긴 사람이 게임을 이긴다.

 

koosaga와 cubelover는 님블을 하려고 한다. 두 사람이 모두 최적의 방법으로 게임을 했을 때, 이기는 사람을 출력한다. 게임은 koosaga가 먼저 시작한다.

 

 

입력

첫째 줄에 동전의 개수 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄에는 동전이 놓여져있는 정사각형 칸의 번호 Pi (1 ≤ Pi ≤ 109)가 주어진다.

직사각형의 크기는 항상 1×10¹⁰이다.

 

 

출력

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

 

 

풀이

님 게임의 필승 전략을 사용하는 문제였습니다.

 

특히, "11868번 님게임 2" 상당히 유사한 문제였습니다.

아직 위 문제를 풀어보시지 않은 분은 아래 포스팅을 꼭 정독하시길 바랍니다.

 

 

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

 

 

님블 문제를 잘 읽어보면, 동전을 0으로 보내야한다고 하였습니다.

이것은 님 게임에서 돌 더미를 0개로 만드는 것과 동치합니다.

 

따라서, 각 칸 마다 동전의 개수를 XOR 하여 0이 아니면 선공이 승리하고, 0이면 후공이 승리하도록 소스코드를 짜시면 됩니다.

 

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

 

 

소스코드

 

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