ps:problems:boj:16831
목차
Nim without Zero
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 16831 |
문제명 | Nim without Zero |
레벨 | 플래티넘 2 |
분류 |
게임 이론 |
시간복잡도 | O(n) |
인풋사이즈 | n<=10^5 |
사용한 언어 | Python 3.11 |
제출기록 | 35396KB / 108ms |
최고기록 | 92ms |
해결날짜 | 2023/07/05 |
풀이
- 님 게임의 변형이다. 우선 일반 님게임에서 승리조건이 왜 전체를 xor한 값이 0이 아닌지를 이해하고 있어야한다.
- 이 게임에서의 패배포지션은 가능한 행동이 xor값을 0으로 바꾸는 것밖에 없는 상태이다. 어떠한 파일이든 돌이 2개 이상이 있다면, 돌을 1개 빼냐 2개빼냐에 따라서 다음 xor값이 달라지게 되므로, 적어도 한가지는 xor값을 0이 아닌 상태로 만들수 있다. 그렇다면 패배포지션은 파일들에 돌이 1개 또는 0개밖에 없으면서, 돌이 1개인 파일이 홀수개인 상태이다.
- 님게임과 비슷하게 접근하자. 님게임과 마찬가지로 돌을 가져가는 모든 행동은 xor합을 바꾸게 된다. 패배 포지션은 xor합이 1인 상태이므로, 처음 포지션의 xor합이 1이 아니라면, 선공은 xor합을 1로 만드는 행동을 취해서 상대에게 턴을 넘겨주고, 상대가 xor값을 다시 1이 아닌 상태로 넘겨주면, 다시 xor합을 1로 만들어서 돌려주는 것을 반복하면 된다. 그러면 결국 상대는 패배포지션에 도달하게 된다.
- 님게임과 다른 점은, 님게임에서는 현재 xor합이 얼마이든간에, 그 값을 0으로 바꿀수 있는 행동이 존재했다. 하지만, 1로 바꾸는 것은 얘기가 다른데, 현재 xor합이 0인 상태에서는 1로 바꾸는 행동이 존재하지 않을수도 있다.
- 다행히 현재 xor합이 0이 되면 게임이 끝나기 때문에, 게임 도중에 생기는 그러한 경우는 신경쓰지 않아도 된다. 하지만 게임이 시작했을때의 포지션의 xor합이 0일 가능성은 있는데, 이 때에는 이 포지션에서 xor합을 1로 바꿀수 있는지 없는지를 확인해야 한다. 만약 xor합을 0에서 1로 바꾸려면, 어떤 파일에서 마지막비트만 변환해주면 된다. 0을 1로 바꾸는것은 숫자를 증가시키기 때문에 불가능하고, 1을 0으로 바꿔줘야 한다. 그러려면 마지막 비트가 1인 파일, 즉 돌의 수가 홀수개인 파일이 존재해야 한다.
- 정리하면. 처음 포지션의 xor합이 1이면 선공의 패배. xor합이 2이상이면 선공의 승리. xor합이 0이라면, 홀수개의 돌을 갖는 파일이 존재하면 선공 승리, 아니면 선공 패배이다.
코드
"""Solution code for "BOJ 16831. Nim without Zero".
- Problem link: https://www.acmicpc.net/problem/16831
- Solution link: http://www.teferi.net/ps/problems/boj/16831
Tags: [game theory]
"""
import functools
import operator
import sys
def main():
N = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for _ in range(N)]
grundy = functools.reduce(operator.xor, a)
if grundy == 0:
print('Alice' if any(a_i % 2 == 1 for a_i in a) else 'Bob')
else:
print('Alice' if grundy != 1 else 'Bob')
if __name__ == '__main__':
main()
ps/problems/boj/16831.txt · 마지막으로 수정됨: 2023/07/05 15:13 저자 teferi
토론