사용자 도구

사이트 도구


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이 주어졌다.
  • 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()

토론

댓글을 입력하세요:
T D G U G
 
ps/problems/boj/11694.txt · 마지막으로 수정됨: 2023/06/21 02:01 저자 teferi