[백준] 1017 소수 쌍 (C++)

오늘 학교에서 풀어서 맘에 드는 문제.

1017번: 소수 쌍

 

1.

크기가 짝수인 배열이 주어진다. (배열의 원소는 서로 다르다.)

남는 거 없이 2개씩 짝지어야 한다. 각 짝의 합은 소수가 되어야 한다.

 

2.

어떻게 두 개를 짝지을 수 있을까?

서로 다른 두 수를 더해서 소수가 되는 경우를 살펴보자.

- 짝수끼리 더하면 무조건 짝수니까 소수가 나올 수 없다.

- 홀수끼리 더하면 무조건 짝수니까 소수가 나올 수 없다. (1+1은 소수지만 배열의 원소는 서로 다르다고 했다.)

 

3.

짝수와 홀수를 짝지어야 하니까 홀짝을 기준으로 이분그래프를 모델링하여 합이 소수가 되게 이분매칭을 하자!

이때, (배열의 짝수의 개수 == 배열 내의 홀수의 개수)여야함은 쉽게 알 수 있다. 아니라면 -1 출력하자.

 

4.

이분매칭한 개수가 (배열의 크기/2)와 같지 않으면 조건에 부합하지 않으므로 -1을 출력하자.

 

5.

여기서 끝이 아니다.

가능한 모든 매칭을 찾아야 한다. 모든 매칭마다 배열의 첫 원소가 매칭 된 녀석을 출력해야 하기 때문이다.

 

6.

그러면 이제 또 다른 매칭 방법이 있는지는 어케 찾을까?

 

이분매칭의 논리를 이용하자.

- 일단 첫 원소의 매칭을 끊어준다.

- 첫 원소와 매칭이 가능한 놈이 있으면 매칭 시켜준다.

이를 가능한 모든 경우에 대해 반복하면서 답이 되는 값들을 찾는다.

 

 

 

구현이 쉽지 않다. (내가 어렵게 해서ㅋㅋ)

 

코드

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 998244353
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n;
ll arr[51];
ll sieve[2001];
ll aMatch[1001];
ll bMatch[1001];
ll visited[1001];
vector<ll> even;
vector<ll> odd;
vector<ll> ans;

bool dfs(ll a) {
	if (visited[a]) return false;
	visited[a] = 1;
	for (ll b = 0; b < even.size(); b++) {
		if (!sieve[a + even[b]]) continue;
		if (bMatch[even[b]] == -1 || dfs(bMatch[even[b]])) {
			aMatch[a] = even[b];
			bMatch[even[b]] = a;
			return true;
		}
	}
	return false;
}

ll bipartiteMatch() {
	ll size = 0;
	for (ll from = 0; from < odd.size(); from++) {
		memset(visited, 0, sizeof(visited));
		if (dfs(odd[from])) size++;
	}
	return size;
}

void solve() {
	memset(aMatch, -1, sizeof(aMatch));
	memset(bMatch, -1, sizeof(bMatch));
	cin >> n;
	for (ll i = 1; i <= n; i++) {
		cin >> arr[i];
		if (arr[i] % 2) odd.push_back(arr[i]);
		else even.push_back(arr[i]);
	}
	if (arr[1] % 2 == 0) swap(odd, even);
	if (odd.size() != even.size()) {
		cout << -1 << endl;
		return;
	}

	if (bipartiteMatch() != n / 2) {
		cout << -1 << endl;
		return;
	}

	for (ll i = 0; i < even.size(); i++) {
		if (sieve[odd[0] + even[i]]) {
			ll aa = aMatch[odd[0]];
			ll bb = bMatch[aMatch[odd[0]]];
			bMatch[aMatch[odd[0]]] = -1;
			aMatch[odd[0]] = -1;
			memset(visited, 0, sizeof(visited));
			if (bMatch[even[i]] == -1 || dfs(bMatch[even[i]])) {
				aMatch[odd[0]] = even[i];
				bMatch[even[i]] = odd[0];
				ans.push_back(even[i]);
			}
			else {
				aMatch[odd[0]] = aa;
				bMatch[aMatch[odd[0]]] = bb;
			}
		}
	}
	sort(ans.begin(), ans.end());
	for (ll i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	//에라토스테네스의 체, 1이면 소수
	memset(sieve, 1, sizeof(sieve));
	sieve[1] = 0;
	for (ll i = 2; i <= 2000; i++) {
		for (ll j = 2; i * j <= 2000; j++) {
			sieve[i * j] = 0;
		}
	}
	int tc = 1; //cin >> tc;
	while (tc--) solve();
	return 0;
}