[백준 C++] 21133 N-Queen2

cldhfleks2·2021년 11월 3일
0

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (4 ≤ N ≤ 10,000)

출력

N개의 줄을 출력해야 한다. i번째 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다.

https://www.acmicpc.net/problem/21133

이문제는 그려보면 규칙을 찾을 수 있었다.

간단한 규칙으로 그리다보니 맨아래처럼 출력이나오면됬다.
(하지만 잘못된 풀이임. 아래에서 계속설명)

#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	int c = n / 2; //몫
	for (int i = 0; i < c; i++) {
		printf("%d\n", (i + 1)*2);
	}
	for (int i = 0; i < c; i++) {
		printf("%d\n", (i + 1) * 2 - 1);
	}
	if (n % 2 != 0) printf("%d\n", n);
}

여기까지 푼 코드가 이러한데,

처음에는 코드의 속도가느려서인가해서 바꿨지만, 알고보니 500개의 정답중에 331개만 맞았다는것이다.
나머지가 왜틀렸는가 그림을 다시 살펴보니..

아래 선을 그은것처럼 대각선으로 서로 만나고있었다..

500개중 331면.. 비율이 0.6이라 직감적으로 6배수마다 뭐가 틀렸나싶어서
n=10, 11, 12, 13, 14, 15일떄찾아보니 6k+2, 6k+3일때 오류가 발생하는데..(그림에선 8, 9) 이걸고치기위해
새로운 규칙을 찾아내려했으나 너무 시간이오래걸려서 GG

profile
i will be a developer

0개의 댓글