Problem :

https://www.hackerrank.com/challenges/tower-breakers-1/problem


My Solution :

#!/usr/bin/env python3


def tower_breakers(n, m):
if n % 2 == 1 and m != 1:
return 1
return 2


t = int(input())
for _ in range(t):
n, m = map(int, input().split())
result = tower_breakers(n, m)
print(result)


Comment :

일단 단 한개의 타워가 있다고 가정하자. m이 1이면 P1이 아무런 조치를 취할 수 없다. P2의 승리다. 그 외에는 전부 P1이 승리다. 왜냐하면 1을 남겨버리면 P2가 아무것도 할 수 없기 때문이다.


이번에는 두개의 타워가 있다고 가정하자. 마찬가지로 m이 1이면 P2의 승리이니 논외로 하고, m이 예를 들어 10 정도가 된다고 치자. P1이 첫번째 어떤 행동을 하든 P2는 그냥 따라하기만 하면 된다. 그러면 무조건 P2가 승리하게 되어 있다.


만약 P1이 첫번째 타워를 5로 만들면 P2는 두번째 타워를 5로 만든다. P1이 첫번째 타워를 1로 만들면 P2는 두번째 타워를 1로 만들면 게임은 끝난다. P1이 첫번째 타워를 2로 만들었더라도 P2가 두번째 타워를 2로 만든다면 결국 P1이 마지막 1로 만들고 P2가 1로 만들어 P2의 승리가 된다.


타워의 갯수가 3개면 어떨까? 그럼 P1의 승리이다. P1은 첫번째 타워를 1로 만든다. 그럼 상황이 2개의 타워가 남고 P1이 P2의 지위를 가지게 된다. 위에서 살펴보았듯이 타워의 갯수가 짝수이면 P2가 이길 수 밖에 없다. (따라하기 전략)