BOJ 1017 소수 쌍

문제

지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다.

1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23

또는

1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 예제의 답은 4, 10이다.

입력

첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

출력

첫째 줄에 정답을 출력한다. 없으면 -1을 출력한다.

예제 입력 1

6 1 4 7 10 11 12

예제 출력 1

4 10

풀이

이 문제는 이분 매칭을 응용한 문제이다. 문제에서 주어진 N개의 소수로 이루어진 같은 두 집합 A와 B가 있을 때, A의 원소를 조건에 맞게 B의 원소에 매칭시켜주면 된다. 이때, B에서 어떤 원소가 A의 원소와 매칭되었을 경우, A의 그 원소는 더이상 매칭시킬 필요가 없다. 즉, A의 a를 B의 b와 매칭시킴과 동시에, A의 b를 B의 a과 매칭시키면 된다. 이때, 매칭을 할 조건은 a+b가 소수이면 된다.

 

이 알고리즘을 효율적으로 사용하기 위해 1부터 2000까지의 소수를 전부 구해놓으면 쉽게 할 수 있다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#include <vector>

#define MAX 10000

using namespace std;

vector<int> v;

int arr[MAX]; //원래 배열
int match[MAX]; //어떤 원소와 매칭되어있는지를 나타내는 배열
int visit[MAX]; //이분 매칭에 사용되는 visit배열
int sub[MAX]; //1번째 원소와 어떤 원소를 제거한 배열
int isnotprime[MAX]; //소수일 경우에는 1, 아니면 0
int ans[MAX]; //1번째 원소와 i번째 원소를 매칭하는 것이 가능하면 0, 아니면 1

bool dfs(int x, int N) //x번째 원소를 매칭하는 것이 가능하면 매칭한 후 true 반환, 아니면 false 반환
{
	if (visit[x] == 1)
	{
		return false;
	}

	visit[x] = 1;

	int i;
	for (i = 1; i <= N; i++)
	{
		if ((isnotprime[sub[x] + sub[i]] == 0) && (i != x))
		{
			if (match[i] == 0 || dfs(match[i], N))
			{
				match[i] = x;
				match[x] = i;
				return true;
			}
		}
	}

	return false;
}

int main(void)
{
	int N;
	scanf("%d", &N);

	int i, j, k;
	for (i = 1; i <= N; i++)
	{
		scanf("%d", &arr[i]);\
	}

	int ptr = 0;

	for (i = 2; i <= 3000; i++) //넉넉잡아 3000
	{
		if (isnotprime[i] == 0)
		{
			for (j = 2 * i; j <= 3000; j += i)
			{
				isnotprime[j] = 1;
			}
		}
	}

	for (i = 2; i <= N; i++)
	{
		ptr = 0;
		for (k = 1; k <= N - 2; k++) //이분매칭에 필요한 배열 초기화
		{
			visit[k] = 0;
			match[k] = 0;
		}
		if (isnotprime[arr[1] + arr[i]]) //1과 i가 매칭 가능한지 확인
		{
			ans[i] = 1;
			continue;
		}
		for (j = 1; j <= N; j++) //매칭 가능할 경우 1과 그 원소를 제거한 배열 만들기
		{
			if (j != 1 && j != i)
			{
				sub[++ptr] = arr[j];
			}
		}

		for (j = 1; j <= N - 2; j++)
		{
			if (match[j] != 0)
			{
				continue;
			}

			for (k = 1; k <= N - 2; k++)
			{
				visit[k] = 0;
			}

			if (!dfs(j, N - 2))
			{
				ans[i] = 1;
				break;
			}
		}
	}

	int cnt = 0;

	for (i = 2; i <= N; i++)
	{
		if (ans[i] == 0)
		{
			v.push_back(arr[i]);
			cnt++;
		}
	}

	if (cnt == 0)
	{
		printf("%d\n", -1);
		return 0;
	}

	sort(v.begin(), v.end());

	for (i = 0; i < v.size(); i++)
	{
		printf("%d ", v[i]);
	}
	printf("\n");

	return 0;
}