백준 11871번: 님 게임 홀짝 (Python)

문제

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'를 출력한다.

 

 

---

 

풀이

대충 머리 좀 굴리면 해법을 찾을 수 있는 문제인가 싶었는데, 전혀 감이 안 잡히더라. 그래서 그런디 수도 찾아보고, 스프라그-그런디 정리도 공부했다. 게임이론 재밌다.

1. 문제 푸는데 가장 도움이 된 소스: https://tataky.tistory.com/2

BOJ 게임 문제 스페셜

2. 그런디 수를 구하려면 왜 집합에서 없는 가장 작은 정수를 고르는지, 왜 그런디 수의 합 연산(==  행동 집합간의 "+" 연산) 은 그런디 수끼리의 bitwise xor 연산인지, 왜 그란디 수가 *0이면 후공이 이기고, *0이 아니면 선공이 이기는지 등에 대한 궁금증을 해결하고 싶다면:

https://casterian.net/archives/1239

필승 전략 게임: 스프라그-그런디 정리(Sprague-Grundy Theorem)와 그런디 수(Grundy Number), 님 게임(Nim Game

(수학에 익숙하지 않으면 notation이라든가, '집합을 수처럼 보는 느낌' 등이 생소해서 읽기 어려울 듯하다.)

영문 위키피디아에서 스프라그-그런디 정리가 있는데, 위 링크가 한글이기도 하고, 설명도 더 자세해서 이해하기 편하다.

PS. 'cubelover'를 'clublover'로 적어서 계속 왜 틀렸지? 하면서 시간을 버렸다... ㅎㅎ;;

 

코드

N = int(input())
nums = list(map(int, input().split()))

def grundy(n: int)-> int:
    return (n+1) // 2 if n % 2 == 1 else (n-2) // 2

xor = 0
for num in nums:
    xor ^= grundy(num)

print("cubelover" if xor == 0 else "koosaga")