문제 상황
Amal과 Bimal이 초콜릿을 이용한 게임을 하고 있다고 가정해 보겠습니다. 두 사람에게는 초콜릿이 하나 이상 담긴 n개의 용기가 있으며, 용기에는 1부터 N까지 번호가 붙어 있고 i번째 용기에는 count[i]개의 초콜릿이 들어 있습니다.
게임 규칙은 다음과 같습니다.
- 첫 번째 플레이어가 용기 하나를 골라 그 안에서 초콜릿을 한 개 이상 꺼냅니다.
- 두 번째 플레이어가 비어 있지 않은 용기를 골라 같은 방식으로 초콜릿을 가져갑니다.
- 두 사람은 이 과정을 번갈아 반복하며, 자신의 차례에 더 이상 가져갈 초콜릿이 없는 플레이어가 패배합니다.
Amal이 먼저 시작할 때, 어떻게 진행되더라도 반드시 승리하도록 첫 수를 둘 수 있는 방법이 총 몇 가지인지 구하는 것이 목표입니다.
예시로 이해하기
입력이 count = [2, 3]이라면 정답은 1입니다. 초기 상태는 [2, 3]이며, 유일한 승리 첫 수는 다음과 같습니다.
- Amal이 두 번째 용기에서 초콜릿 하나를 가져가 [2, 2]를 만듭니다.
- Bimal이 첫 번째 용기에서 하나를 가져가면 [1, 2]
- Amal이 다시 두 번째 용기에서 하나를 가져가면 [1, 1]
- Bimal이 첫 번째 용기에서 하나를 가져가면 [0, 1]
이처럼 Amal이 [2, 2]라는 대칭 상태를 만들면, 이후 Bimal이 무엇을 하든 Amal이 같은 양만큼 되돌려 놓는 전략으로 항상 마지막 초콜릿을 가져갈 수 있습니다. 반면 첫 번째 용기에서 초콜릿을 가져오는 첫 수는 승리를 보장하지 못하므로, 가능한 첫 수는 1가지뿐입니다.
풀이 접근 방법
이 문제는 게임 이론의 님(Nim) 게임 원리를 이용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 모든 용기의 초콜릿 개수를 XOR 연산한 값을 tmp라고 합니다.
- tmp가 0이면 현재 위치는 이미 패배 위치이므로, 승리를 보장하는 첫 수는 존재하지 않습니다. 따라서 0을 반환합니다.
- tmp가 0이 아니라면, 각 용기에 대해 (tmp XOR c) < c를 만족하는지 확인합니다. 이 조건을 만족하는 용기에서 초콜릿을 가져와 개수를 tmp XOR c로 맞추면, 남은 전체 XOR 값이 0이 되어 상대를 패배 위치로 몰아넣을 수 있습니다.
- 따라서 (tmp XOR c) < c를 만족하는 용기의 개수를 세어 반환하면 됩니다.
구현 예제
다음 파이썬 코드로 위 알고리즘을 확인해 보겠습니다.
def solve(count):
tmp = 0
for c in count:
tmp ^= c
if not tmp:
return 0
else:
moves = 0
for c in count:
moves += (tmp^c) < c
return moves
count = [2, 3]
print(solve(count))입력
[2, 3]
출력
1
복잡도 분석
- 시간 복잡도: O(n) — 용기 배열을 두 번 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.