사용자 도구

사이트 도구


ps:problems:boj:32871

돌 게임 nm

ps
링크acmicpc.net/…
출처BOJ
문제 번호32871
문제명돌 게임 nm
레벨실버 2
분류

게임 이론

시간복잡도O(T)
인풋사이즈T<=100,000
사용한 언어Python 3.13
제출기록32412KB / 164ms
최고기록132ms
해결날짜2025/01/18

풀이

  • 모든 포지션을 두 가지 그룹으로 나눠서 풀 수 있는 게임이론 문제
  • 일단.. 보드에서 어떤 열, 어떤 행에 돌이 있는지는 중요하지 않다. 돌이 놓여져있는 열과 행의 개수가 각각 몇개인지만 중요하다.
  • 따라서 액션 역시, 어떤 열을 골라서 돌을 제거하는지는 상관 없다. 의미있는 액션은 하나의 열을 제거하는 액션과, 하나의 행을 제거하는 액션 이렇게 두가지 뿐이다.
  • 돌이 있는 열의 개수가 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()

토론

댓글을 입력하세요:
J B​ A A​ R
 
ps/problems/boj/32871.txt · 마지막으로 수정됨: 2025/01/18 14:32 저자 teferi