글 읽기 - N Queen 문제 시간 10초

ohwonteak 3년 전 0

컴퓨터에서 VS2017에서 릴리즈모드로 N이 14일때에 대략 17초 정도가 걸려서 뭔가 더 수정해야 하나 싶었는데 제출 해보니 통과가 되서 궁금한 것이 이 문제에서 예제 돌릴때 N이 14인 것도 들어가나요?

#include <iostream>
#include <vector>
#include <iostream>
using namespace std;
int N;
int ans;


void solved(int cur_x, std::vector<int> vec_y
	, std::vector<int> vec_minus_linear
	, std::vector<int> vec_plus_linear) {
	//어차피 재귀함수에서 다음 재귀로 넘어갈때 x를 x+1로 넘기므로 x유무판단은 필요가 없다.
	for (int y = 0; y < N; y++) {

		if(vec_y[y]== 1 ||  vec_plus_linear[-cur_x + y + N -1 ] == 1 || vec_minus_linear[cur_x + y] == 1 )  // 예상되는 범위에 존재해서 퀸끼리 만날때
			continue;
		
		if (cur_x == N - 1) {//끝지점에 도착했을 경우 아무 이상없이 퀸끼리 만나지 않는 것이 만들어졌을경우
			ans++;
			continue;
		}

		auto copy_vec_y = vec_y;
		copy_vec_y[y]=1;

		std::vector<int> copy_vec_minus_linear = vec_minus_linear;
		copy_vec_minus_linear[cur_x + y] = 1;

		std::vector<int> copy_vec_plus_linear = vec_plus_linear;
		copy_vec_plus_linear[-cur_x + y + N -1] = 1;

		solved(cur_x + 1, copy_vec_y, copy_vec_minus_linear, copy_vec_plus_linear);


	}

}

int main() {
	cin >> N;

	solved(0, std::vector<int>(N,0), std::vector<int>(2*N-1,0), std::vector<int>(2*N-1,0));
	printf("%d\n", ans);


	return 0;
}

Green55 3년 전 1

네 포함되어 있습니다.

백준 서버가 원래 꽤 빠릅니다.

Green55 3년 전 1

이런 경우에는 assert 문을 걸어서 제출해보시면 직접 확인해보실 수 있습니다.

ohwonteak 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

N Queen 문제 시간 10초

ohwonteak 3년 전 0

Green55 3년 전 1

Green55 3년 전 1

ohwonteak 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말