백준 16884 (나이트 게임) c++

문제

16884번: 나이트 게임

n * n 체스판에서 A와 B가 체스를 두는데 서로 체스 말을 '나이트'로 고정하고 번갈아가면서 나이트가 공격할 수 없는

공간에다가 나이트를 둡니다. 선공은 A가 먼저하고 승리하는 사람을 출력해주면 되는 문제입니다.

 

손으로 그림을 그려가면서 규칙성을 찾아보려 했지만 찾을 수 없었고 외부 블로그에서 영감을 얻어 해결하였습니다.

 

먼저 후공인 B가 이기는 최선의 방법을 구하는 것입니다.

 결론 부터 얘기하면 B는 A가 두는 나이트의 점대칭 인곳에 체스를 두게 되면 최적의 방법이 됩니다.

따라서 A가 어딜 두던 B는 A의 점대칭 위치에만 체스를 두면 승리하게 됩니다.

하지만 A가 선공의 위치를 바꿀 수 있는 한가지 방법은 A가 체스를 두었을 때 B가 점대칭인곳에 체스를 두지 

못하게 해야 합니다. 그러한 방법은 N * N의 체스판에서 가운데에 두는 방법 밖에 없습니다.

4 X 4 와 3 X 3

N * N 체스판에서 가운데가 있을려면 N이 홀수인 경우 밖에 없으므로 

결국 N이 홀수면 A가 이기고 짝수면 B가 이깁니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		if (n % 2 == 1) cout << "koosaga" << "\n";
		else cout << "cubelover" << "\n";
	}
	return 0;
}