====== 돌 게임 nm ====== ===== 풀이 ===== * 모든 포지션을 두 가지 그룹으로 나눠서 풀 수 있는 게임이론 문제 * 일단.. 보드에서 어떤 열, 어떤 행에 돌이 있는지는 중요하지 않다. 돌이 놓여져있는 열과 행의 개수가 각각 몇개인지만 중요하다. * 따라서 액션 역시, 어떤 열을 골라서 돌을 제거하는지는 상관 없다. 의미있는 액션은 하나의 열을 제거하는 액션과, 하나의 행을 제거하는 액션 이렇게 두가지 뿐이다. * 돌이 있는 열의 개수가 r이고 행의 개수가 c인 포지션을 (r,c)라고 쓰자. * 마지막에 승리하는 포지션은, (1,x) 또는 (x,1)이다. * 그리고 (2,2)는 (1,2)또는 (2,1)로 가게 되므로 패배포지션이다. * 이제, r>1, c>1 인 모든 포지션을, 'r과 c의 홀짝성이 똑같은 포지션'과 'r과 c의 홀짝성이 다른 포지션' 으로 나누자 * 'r과 c의 홀짝성이 똑같은 포지션' 에서는 어떤 액션을 취해도 'r과 c의 홀짝성이 다른 포지션'으로 전환되고, 'r과 c의 홀짝성이 다른 포지션'에서는 어떤 액션을 취해도 'r과 c의 홀짝성이 똑같은 포지션'으로 전환된다. * 그리고, 패배하게 되는 포지션인 (2,2)는 'r과 c의 홀짝성이 똑같은 포지션' 에 포함된다 * 따라서, r>1, c>1 일때에는 'r과 c의 홀짝성이 똑같은 포지션' 이 패배포지션, 'r과 c의 홀짝성이 다른 포지션'이 승리포지션이다. ===== 코드 ===== """Solution code for "BOJ 32871. 돌 게임 nm". - Problem link: https://www.acmicpc.net/problem/32871 - Solution link: http://www.teferi.net/ps/problems/boj/32871 Tags: [game theory] """ import sys def main(): T = int(sys.stdin.readline()) for _ in range(T): n, m = [int(x) for x in sys.stdin.readline().split()] print('YES' if n == 1 or m == 1 or (n + m) % 2 == 1 else 'NO') if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:실버_2}}