대엉코딩

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;
}

www.acmicpc.net/problem/9663

1. 풀이방법

- N개의 퀸을 놓을 수 있는 경우의 수 를 구하는 문제이고, 모든 경우의 수를 탐색하는데 시간을 신경써야합니다.

- 처음에는 그냥 dx[8],dy[8] 을 선언해서 8방향을 모두 탐색하다가 이미 다른 퀸이 있으면 리턴하고 라는 식으로

- 구현을 했다가.....N=5일때 까지 였나...? 까지 밖에 나오지 않았습니다...

- 처음에 N이 최대 14이길래 시간초과는 신경 안써도 되는 줄 알고 짰다가 당황한 문제였습니다.

- 체스판의 특성을 이용하여 x,y좌표의 특징들을 이용해서 놓을 수 있는지를 판단해야 했습니다.

2. 주의사항

- 체스판의 특성을 활용, 시간초과를 주의해야 함.

- 2차원 배열이 아닌 1차원배열을 이용하여 [x]=y를 통해 x,y 좌표를 나타내는 것이 처음에는 생소할 수 있음

3. 나의코드

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

int N;
int resultcount = 0;
int queenarr[15]; //[x]= y
 // 0~ N-1까지 사용
bool checking(int x, int y) {
	for (int i = 0; i < x; i++) {
		if ( abs(y-queenarr[i]) == abs(x -i) || queenarr[i] == y) {
			return false;
		}
	}
	return true;
}
void makecase(int x) {
	if (x == N) {
		resultcount++; return;
	}
	for (int i = 0; i < N; i++) {
		if (checking(x, i)) {
			queenarr[x] = i;
			makecase(x + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	makecase(0);
	cout << resultcount << "\n";
	return 0;
}