글 읽기 - 소수쌍 질문입니다.

cubalys 8년 전 0

홀수 + 홀수 짝수 + 짝수 는 소수가 될 수 없으므로

홀수 배열과 짝수 배열로 나눈 후

첫 수가 홀수라면 홀수기준, 짝수라면 짝수 기준으로 MAP을 만들었습니다.

ex) 6 \n 1 2 3 4 5 6

이 들어온다면

2 4 6

5 7

2 6

의 맵이 만들어 지게 됩니다.

6 \n 2 1 3 4 5 6

이 들어온다면

1 3 5

1 3

1 5

의 맵이 만들어지게 됩니다.

그 이후에 DFS를 통해 check되지 않은 수들을 검사하며

맨 아래까지 짝지어 지는 경우

첫 수와 짝지어진 수를 R이라는 배열에 넣은 뒤

flag를 1로 하여

x가 0이 될떄까지 return 되도록 했습니다.

어디에서 틀렸는지 모르겠습니다.

#include <iostream>
#include <algorithm>
using namespace std;
bool Prime[2000] = {1, 1, }, check[25], O_E, flag; // O_E -> 첫 수가 홀수인지 짝수인지
int Odd[25], Even[25], O, E, MAP[25][25], Size[25], R[25], P, N;
void PRIME(){
	for(int i = 2; i<2000; i++)
		if(!Prime[i])
			for(int j = i+i; j<2000; j+=i)
				Prime[j] = 1;
}
void input(){
	int num;
	cin>>N>>num;
	num&1 ? (O_E = 0, Odd[O++] = num) : (O_E = 1, Even[E++] = num); 
	for(int i = 1; i<N; i++)
		cin>>num, (num&1)? Odd[O++] = num : Even[E++] = num;
	for(int i = 0; O_E ? i < E : i < O; i++){ // 첫 수가 홀수면 홀수를 기준으로 짝수면 짝수를 기준으로 MAP을 만든다.
		P = 0;
		for(int j = 0; O_E ? j < O : j< E; j++)
			if(!Prime[Even[O_E ? i:j] + Odd[O_E?j:i]]) MAP[i][P++] = j;
		Size[i] = P;
	}
}
void DFS(int x, int y, int z){
	if(x == N/2) {flag = 1;R[P++] = O_E? Odd[z]:Even[z];return;}
	if(y > -1) check[y] = 1;
	for(int i = 0; i<Size[x]; i++){
		if(check[MAP[x][i]] == 0) DFS(x+1, MAP[x][i], x==0?MAP[x][i]:z); // 해당 수를 사용하지 않았다면 탐색
		if(flag){ // 전부 탐색했다면 탐색하지 않고 Return
			check[y] = 0;
			if(x == 0) {flag = 0; continue;}
			return;
		}
	}
	check[y] = 0;
}
int main(){
	PRIME();
	input();
	if(O!=E) {cout<<-1<<endl; return 0;}
	P = 0;
	DFS(0, -1, 0);
	if(P == 0) cout<<-1<<endl;
	else{
		sort(R, R+P);
		for(int i = 0; i<P; i++) cout<<R[i]<<" ";
		cout<<endl;
	}
}

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

문제

문제

출처

ICPC

소수쌍 질문입니다.

cubalys 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말