Problem :

https://www.hackerrank.com/challenges/game-of-stones-1/problem


My Solution :

#!/usr/bin/env python3


def game_of_stones(n):
if n % 7 in (0, 1):
return 'Second'
return 'First'


t = int(input())
for _ in range(t):
n = int(input())
result = game_of_stones(n)
print(result)


Comment :

베스킨라빈스31 게임과 비슷하다. 1부터 쭈욱 올라가다 보면 규칙을 발견할 수 있게 된다. 선택할 수 있는 숫자는 2,3,5 세가지 뿐이기 때문에 7을 기준으로 순환하게 된다. mod 7 기준 표로 아래와 같다.



두 플레이어가 모두 똑똑하다면, 최초 입력된 숫자의 mod 7 결과 값에 따라 승패는 결정나버리게 된다. 만약 mod 7이 3으로 들어왔다고 가정하자. 그럼 Player1이 이긴 경기가 된다. 왜냐하면 Player1은 5를 선택해 1을 만들게 된다. 그럼 Player2가 어떤 선택을 하든 Player1은 다시 0,1을 만들 수 있다. 즉 Player2의 선택에 따라 Player1이 합을 6~8을 만들어낼 수 있기 때문에  0,1 사이를 왔다 갔다 할 수 있다는 말이다.


베스킨라빈스31 게임도 마찬가지이다. 그 게임은 1,2,3을 말할 수 있고 31을 말하는 사람이 지는 게임이다. 보통 여러명이 하지만, 만약 두명이서 그 게임을 한다면 무조건 첫번째 하는 사람이 이길 수 밖에 없다. 왜냐하면 31을 말하는 사람이 지기 때문에, 반대로 말하면 30을 말하는 사람이 이기게 된다. 따라서 첫번째 플레이어가 2를 부르면 게임은 끝난다. 그 다음부터는 상대방이 뭘 말하든 합이 4가 되도록 대응하면 된다. 그러면 자신이 30을 부를 수 있게 된다.


따라서 베스킨라빈스31 게임을 둘이서 하는건 아무런 의미가 없다. 만약 하게 되면 첫번째로 2를 부르면 이긴다. 만약 상대방이 그 내용을 모르고 1을 부르면 1로 대응하여 2 mod 4 == 2를 만들고, 3을 부르면 3으로 대응해 6 mod 4 == 2를 만들면 된다. 그 다음부턴 4의 보수를 계속해서 말하면 이기게 된다.