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()
ps/problems/boj/32871.txt · 마지막으로 수정됨: 2025/01/18 14:32 저자 teferi
토론