글 읽기 - 소수쌍문제 시간초과 질문입니다.

cubalys 8년 전 0

제 알고리즘은

SUM 구조체 배열에 합이 소수가 되는 경우를 넣어 두고

DFS를 통해

다른 쌍이 있을 경우 계속 탐색을 진행하여

모든 수가 쌍이 된 경우(깊이가 N/2인 경우)

0번 칸의 수와 짝지었던 수를 배열에 넣은 뒤

flag변수를 1로 해

나머지는 더 검사하지 않도록 했습니다.

어떻게 시간초과를 해결해야 하는지 모르겠습니다

아예 방법을 바꿔야 하나요

#include <iostream>
#include <algorithm>
using namespace std;
bool Prime[2001], check[50], flag;
int A[50], N, R[50], P, K, p;
struct H{
	int x, y;
}SUM[1250];
void DFS(int X, int Y, int cnt){
	if (cnt == N / 2) { R[P++] = A[K], flag = 1;  return; }
	check[X] = check[Y] = true;
	for (int i = 0; i < p; i++){
		if (flag){ check[X] = check[Y] = false; return; }
		if (check[SUM[i].x] == 0 && check[SUM[i].y] == 0) DFS(SUM[i].x, SUM[i].y, cnt + 1);
	}
	check[X] = check[Y] = false;
}
int main(){
	Prime[0] = Prime[1] = true;
	for (int i = 2; i < 2001; i++)
		if (!Prime[i])
			for (int j = i + i; j < 2001; j += i)
				Prime[j] = true;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++)
			if (!Prime[A[i] + A[j]]) SUM[p].x = i, SUM[p++].y = j;
	for (int i = 1; i < N; i++)
		if (!Prime[A[0] + A[i]])
			flag = 0, K = i, DFS(0, i, 1);
	if (P == 0) cout << -1 << endl;
	else{
		sort(R, R + P);
		for (int i = 0; i < P; i++)
			cout << R[i] << " ";
		cout << endl;
	}
}  

rlatkddn212 8년 전 0

움.. 혹시나 해서 flag값들 bit연산으로 관리하면서 동적계획법 사용해봤는데 시간 초과 나오네용.. ㅠ.ㅠ 어렵당..

rlatkddn212 8년 전 0

생각해보니 2개씩 짝맞추는 문제군용 :)

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

문제

문제

출처

ICPC

소수쌍문제 시간초과 질문입니다.

cubalys 8년 전 0

rlatkddn212 8년 전 0

rlatkddn212 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말