대엉코딩

www.acmicpc.net/problem/2726

1. 풀이방법

- 처음에는 백트래킹을 이용한 모든 경우의수를 탐색하는 코드로 짰으나, 시간이 너무 오래걸립니다.

- 문제를 보면 N은 최대 1000이나 되기 때문에 다른방법을 찾아야 했고,

- 어쩔수 없이 직접 그려보며 규칙을 찾아야 했습니다......후... 근데 규칙 찾기도 상당히 난해합니다.

- 테스트케이스를 그리다 보면 어느정도 규칙이 보이는데, 문제는 시작점입니다.

- 시작점을 특정하는 것이 매우 어려웠습니다.

- 그림을 쭉 테스트케이스처럼 그려보다보면  (여기서 N=3 일 때는 테스트 케이스는 (1,1),(3,2)라고 했지만,

- 이것을 (2,1),(3,3)으로 바꿔서 생각하면 테스트케이스에서 어느정도의 일관성을 가진 규칙이 보입니다.) 

- 문제는 시작점을 특정하는 것인데 그려놓고 계속 보다보면 먼저 퀸의 개수가 측정이 가능한데

- (1,1,2,3,3,4,5,5,6,7,7,8,9,9,10,11,11,12......) 이런식입니다.

- 그래서 퀸의 개수를 먼저 배열에 싹다 구해서 넣어놓습니다.

- 그리고 시작점 (X,1)을 찾아야 하는데 이건 제가 찾은 규칙은 (N-퀸의개수+1)이였습니다

- 나머지는 부분은 테스트케이스를 직접 그려놓은 것을 바탕으로 구현하시면 됩니다.

2. 주의사항

- 특이하게도, 백트래킹으로 짠 시간초과가 나는 코드를 이용해서 규칙을 찾는데에 도움을 받아 풀었습니다.

(약 10~11정도까지는 조금 기다리면 나옵니다.) --> 이 코드로 1~11을  써가며 규칙을 찾아 풀었습니다.

3.나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int t;
int n;
int qarr[1005];

void initqueen() {
	int tmpq = 1;
	int index = 1;
	while (1) {
		if (index > 1000) break;
		qarr[index + 0] = tmpq;
		qarr[index + 1] = tmpq;
		qarr[index + 2] = tmpq + 1;
		tmpq += 2;
		index += 3;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	initqueen();
	cin >> t;
	while (t--) {
		cin >> n;
		int startx = n - qarr[n] + 1;
		int starty = 1;
		int tmpx = 1;
		cout << qarr[n] << "\n";
		int tsize = qarr[n];
		while (tsize--) {
			cout << startx << " " << starty << "\n";
			if (startx == starty) {
				tmpx++;
				startx += 1;
				starty = tmpx;
				continue;
			}
			startx += 1; starty += 2;
		}
	}
	return 0;
}