[백준] 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을 출력한다.

 

두개의 숫자는 합이 소수면 짝지을 수 있습니다. 최대한 많은 짝을 만드는게 문제입니다.

이분매칭을 사용하는 문제입니다.

보통 이분매칭은 이분그래프에서 사용하는 알고리즘입니다.

a에서 b를 매칭을 하면, b는 자동으로 a와 매칭이 되어야합니다.

 

우선 첫번째 수와 가능한 다른 수들을 모두 매칭해봅니다.

그 이후에, 남은 숫자끼리 모두 매칭할 수 있다면 정답입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,1,1,-1 }, dx[] = { 1,1,-1,-1}, INF = 987654321;
int N, v[51], s[51], d[51], num[51],u[51], cnt;
vi ans, adj[51];
bool dfs(int k) {
	if (v[k])return false;
	v[k] = 1;
	for (int r : adj[k]) {
		if (d[r])continue;
		if (!s[r] || dfs(s[r])) {
			s[k] = r;
			s[r] = k;
			return true;
		}
	}
	return false;
}
bool isp(int k) {
	for (int i = 2; i <= (int)sqrt(k); i++) {
		if (k % i == 0)return false;
	}
	return true;
}
int main() {
	FAST;
	cin >> N;
	REP(i, N) {
		cin >> num[i];
	}
	REP(i, N) {
		REP(j, N) {
			if (i >= j)continue;
			if (isp(num[i] + num[j])) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	for (int r : adj[1]) {
		mset(s);
		mset(d);
		cnt = 0;
		d[1] = 1;
		d[r] = 1;
		for (int i = 2; i <= N; i++) {
			mset(v);
			if (!d[i] && !s[i]) {
				if (dfs(i))cnt++;
			}
		}
		if (cnt == (N - 2) / 2) {
			ans.push_back(num[r]);
		}
	}
	if (ans.empty()) {
		cout << -1;
		return 0;
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	for (auto r : ans) {
		cout << r << " ";
	}
}