사용자 도구

사이트 도구


ps:problems:boj:27871

Singularity of the Nim

ps
링크acmicpc.net/…
출처BOJ
문제 번호27871
문제명Singularity of the Nim
레벨플래티넘 1
분류

게임 이론

시간복잡도O(T)
인풋사이즈T<=?
사용한 언어Python 3.11
제출기록60548KB / 488ms
최고기록460ms
해결날짜2023/06/16

풀이

  • 한번에 가져갈수 있는 코인 갯수의 제한이 없다고 가정하고 생각해보자 (사실은 문제를 잘못 읽어서 이걸 생각해보게 된거였지만…)
  • 승리하는 액션은, 맨 아래 계단에만 코인이 남아있을때, 그 코인들을 싹 가져가는 것이다. 그리고 다른 계단에서 코인을 가져가는 것은, 계단의 위치와 갯수에 무관하게 맨 아래 계단에 코인을 추가하게 된다.
  • 이것을 잘 조합하면 이런 전략이 가능하다. 내 차례에는 무조건 맨 아래 계단에서 코인을 전부 가져간다. 상대방 턴에는 맨 아래 계단이 비어있기 때문에 맨 아래 계단에서 코인을 가져가는 액션이 불가능하다. 상대방이 할수없이 다른 곳에서 코인을 가져가면 맨 아래 계단에 코인이 생기게 되고, 나는 다시 맨 아래 계단에서 코인을 전부 가져가는 액션을 취할수 있다. 끝없이 반복하면, 결국 마지막 승리액션은 나에게 차례가 돌아온다.
  • 이 전략으로 승리할수 있는 조건은 처음 시작할때 맨 아래 계단에 코인이 1개 이상 있는 것이다. 처음 포지션에 맨 아래 계단이 비어있으면, 상대가 이 전략을 써서 이기게 된다.
  • 이제, 가져갈수 있는 코인의 최대 갯수가 P개로 제한된 경우로 확장해보자. 맨 아래 계단에서 코인들을 남김없이 가져가는 것이 승리하는 액션이 된다는 것은 동일하고, 이것을 내가 하기 위한 전략은 배스킨라빈스와 비슷해진다. 내 차례에서는 맨 아래 계단의 코인의 갯수가 (P+1)의 배수가 되도록 만드는 것을 반복하면 된다. 상대방이 다른 계단에서 어떤 액션을 취하더라도 맨 아래 계단의 코인 갯수는 1~P개만 증가하게 되므로, 내 차례에서 증가한만큼 다시 가져가면 (P+1)의 배수로 계속 유지할수 있다.
  • 결국, 승리 포지션은 맨 아래 계단의 코인 갯수가 (P+1)의 배수가 아닌 모든 경우이다.

코드

"""Solution code for "BOJ 27871. Singularity of the Nim".

- Problem link: https://www.acmicpc.net/problem/27871
- Solution link: http://www.teferi.net/ps/problems/boj/27871

Tags: [game theory]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        # pylint: disable=unused-variable
        N, P = [int(x) for x in sys.stdin.readline().split()]
        C = [int(x) for x in sys.stdin.readline().split()]

        print('First' if C[0] % (P + 1) != 0 else 'Second')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N S Z I Z
 
ps/problems/boj/27871.txt · 마지막으로 수정됨: 2023/06/16 06:27 저자 teferi