※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 32871번 문제인 돌 게임 nm이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/32871
n행 m열의 돌에서 어떤 행을 지우더라도 n-1행 m열의 돌이 놓여있는 상황과 같아지고, 어떤 열을 지우더라도 n행 m-1열의 돌이 놓여있는 상황과 같아짐을 관찰하자. 또한 행 또는 열이 하나만 남아있다면 그 행 또는 열을 지우는 것으로 항상 이길 수 있다는 점을 관찰하자.
위의 관찰을 이용하면 2행2열의 상황에서는 어떤 행 또는 열을 지워도 해당 차례에 돌을 가져가는 사람이 지게 된다. 또한 그렇지 않은 경우 항상 행 또는 열이 하나만 남게 되는 상황을 피해 돌을 가져갈 수 있다.
남은 경우 중에서 행과 열의 합이 홀수인 경우 어떻게 행동을 하더라도 행과 열의 합이 짝수가 되며, 행과 열의 합이 짝수이고 2행2열이 아닌 경우 어떻게 행동을 하더라도 행과 열의 합이 홀수가 되므로, 앞서 분류한 상황을 제외하면 행과 열의 합이 홀수인 경우 해당 차례에 돌을 가져가는 사람이 이기고 그렇지 않을 경우 해당 차례에 돌을 가져가는 사람이 진다는 점을 알 수 있다.
이를 이용하여 문제를 해결하자.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
typedef long long ll;
int T;
ll N, M;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--) {
cin >> N >> M;
if (N == 1 || M == 1 || ((N + M) & 1)) cout << "YES\n";
else cout << "NO\n";
}
}
'BOJ' 카테고리의 다른 글
[BOJ 32902 // C++] Chips (1) | 2024.12.09 |
---|---|
[BOJ 32916 // C++] Another Brick in the Wall (1) | 2024.12.06 |
[BOJ 32760 // C++] Nothing Everything (0) | 2024.12.05 |
[BOJ 32752 // C++] 수열이에요? (1) | 2024.12.04 |
[BOJ 32749 // C++] 타노수 (0) | 2024.12.03 |