백준 1017 / C++

https://www.acmicpc.net/problem/1017

1017번: 소수 쌍

 

[ 풀이 ]

홀짝성을 기준으로 이분그래프로 모델링하자.  a[0]가 있는쪽을 왼쪽집합으로 두자. 

전부 소수가 되게 매칭을 하려면 우선 왼쪽,오른쪽 집합 크기가 같아야 하고, 

최대매칭의 크기가 집합 크기와 같아야 한다. 

이제 a[0]와 매칭되는 걸 출력까지 해야되기 때문에 a[0]와 매칭될 수를 먼저 선택한다. 

이제 나머지 그래프에서 최대매칭이 크기-1 이 되면 성공한 매칭이 된 것이다. 

이 매칭된 수를 모아서 출력해주면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
vector<int>odd, even, lv, rv, ans;
int n, m, p[2222], par[55], vis[55], a[55];

// prime test
void eratoss() {
	p[2] = 1;
	for (int i = 3; i <= 2000; i += 2) p[i] = 1;
	for (int i = 3; i <= 2000; i += 2) {
		if (!p[i]) continue;
		for (int j = i; i * j <= 2000; j += 2) {
			p[i * j] = 0;
		}
	}
}

int match(int x) {
	for (int nx : rv) {
		if (vis[nx] || !p[a[x] + a[nx]])continue;
		vis[nx] = 1;
		if (!~par[nx] || match(par[nx])) {
			par[nx] = x;
			return 1;
		}
	}
	return 0;
}

// a[0] .... a[select] matching
void solve(int select) {
	int ret = 0;
	memset(par, -1, sizeof(par));
	for (int i = 1; i < lv.size(); i++) {
		memset(vis, 0, sizeof(vis));
		vis[select] = 1; // 방문처리
		ret += match(lv[i]);
	}
	if (ret == lv.size() - 1) ans.push_back(a[select]); // 매칭 성공
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	eratoss();
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] % 2) odd.push_back(i);
		else even.push_back(i);
	}
	// lv: 왼쪽 집합, rv: 오른쪽 집합 
	if (a[0] % 2) {
		lv = odd, rv = even;
	}
	else {
		lv = even, rv = odd;
	}
	// 불가능 
	if (lv.size() != rv.size()) {
		cout << -1;
		return 0;
	}
	// a[0]와 매칭시켜보고 solve 수행 
	for (int v : rv) {
		if (p[a[0] + a[v]])solve(v);
	}
	// 출력
	if (ans.size()) {
		sort(ans.begin(), ans.end());
		for (int i : ans) cout << i << " ";
	}
	// 불가능 
	else cout << -1;
}