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()
ps/problems/boj/27871.txt · 마지막으로 수정됨: 2023/06/16 06:27 저자 teferi
토론