ps:problems:boj:11694
님 게임
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 11694 |
문제명 | 님 게임 |
레벨 | 플래티넘 2 |
분류 |
게임이론 |
시간복잡도 | O(n) |
인풋사이즈 | n<=100 |
사용한 언어 | Python 3.11 |
제출기록 | 34248KB / 80ms |
최고기록 | 40ms |
해결날짜 | 2023/06/17 |
풀이
- 스프라그 그런디 정리의 가장 기본이 되는 님 게임이지만, 여기에서는 흔히 주어지는 Normal Nim이 아니라, 마지막 막대를 가져가는 사람이 패배하는 Misère Nim이 주어졌다.
- normal nim 버전의 문제는 님 게임 2 에 있다
- Misère Nim의 승리 포지션은 모든 파일에 막대기가 1개씩만 남았을때를 제외하고는 normal nim과 동일하다. 모든 파일에 막대기가 1개씩만 남았을때에는 파일의 갯수가 홀수개일때가 승리포지션이다. 그외에는 똑같이 grundy 수가 0보다 크면 승리할수 있다.
코드
"""Solution code for "BOJ 11694. 님 게임".
- Problem link: https://www.acmicpc.net/problem/11694
- Solution link: http://www.teferi.net/ps/problems/boj/11694
Tags: [game theory]
"""
import functools
import operator
def main():
N = int(input())
P = [int(x) for x in input().split()]
if max(P) == 1:
print('koosaga' if N % 2 == 0 else 'cubelover')
else:
grundy = functools.reduce(operator.xor, P)
print('koosaga' if grundy != 0 else 'cubelover')
if __name__ == '__main__':
main()
ps/problems/boj/11694.txt · 마지막으로 수정됨: 2023/06/21 02:01 저자 teferi
토론