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;
}
'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
백준 19237 [C++] (0) | 2021.03.05 |
---|---|
백준 17140 [C++] (0) | 2021.01.24 |
백준 10993 [C++] (0) | 2021.01.16 |
백준 20061 [C++] (0) | 2020.12.28 |
백준 20056 [C++] (0) | 2020.12.23 |