[BOJ] 백준 1017번: 소수쌍

소수 = 홀수 + 짝수의 조합으로만 가능한 아이디어를 시작으로

홀수와 짝수를 두 개의 그룹으로 나눠, 시작하는 수의 짝을 고정하여 이분매칭을 반복하는 문제

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef long long ll;
bool s[2001] = { 0, };
int arr[1001];
int ma[1001];
int curd;
bool visit[1001];
int _lsize, _rsize;
vector<int> l, r;
bool dfs(int node) {
	if (visit[node]) return false;
	visit[node] = true;
	for (int i = 0; i < _rsize; i++) {
		if (i != curd && !s[l[node]+r[i]]) { // 지정 x , 소수 
			if (-1 == ma[i] || dfs(ma[i])) {
				ma[i] = node;
				return true;
			}
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	s[0] = 1;
	s[1] = 1;
	for (int i = 2; i < 2001; i++) {
		if (!s[i]) {
			for (int j = i + i; j < 2001; j += i) {
				s[j] = 1;
			}
		}
	}
	int n;
	cin >> n;
	int start;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	start = arr[0];
	if (start & 1) {
		for (int i = 0; i < n; i++) {
			if (arr[i] & 1) {
				l.push_back(arr[i]);
			}
			else {
				r.push_back(arr[i]);
			}
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			if (arr[i] & 1) {
				r.push_back(arr[i]);
			}
			else {
				l.push_back(arr[i]);
			}
		}
	}
	_rsize = r.size();
	_lsize = l.size();
	if (_lsize != _rsize) {
		cout << -1;
		return 0;
	}
	sort(r.begin(), r.end());
	int flag = 0;
	for (int i = 0; i < _rsize; i++) {
		if (!s[l[0] + r[i]]) {
			memset(ma, -1, sizeof(ma));
			curd = i;
			ma[i] = 0;
			int ans = 1;
			for (int j = 1; j < _lsize; j++) {
				memset(visit, 0, sizeof(visit));
				if (dfs(j)) {
					ans += 1;
				}
			}
			if (ans == _lsize) {
				flag = 1;
				cout << r[i] << " ";
			}
		}
	}
	if (!flag) {
		cout << "-1";
	}

}