취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1017번 문제인 소수 쌍이다.
문제는 아래 링크를 확인하자.

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

2를 제외한 모든 소수는 홀수이고 서로 다른 두 자연수의 합은 2가 될 수 없다는 점을 눈여겨보자.

두 수의 합이 소수가 되게 하려면 수 하나는 짝수에서, 다른 수 하나는 홀수에서 골라야한다는 점을 알 수 있다.

각 수를 노드로 하고, 합이 소수가 되는 두 수(하나는 홀수, 하나는 짝수일 수밖에 없다) 사이에 에지를 그으면 이분그래프(bipartite graph)를 하나 얻을 수 있다. 첫 노드와 이어지는 노드를 하나하나 고정해서 이분매칭을 구해보자.

이분매칭의 시간복잡도가 O(VE) = O(N^3)이고 노드를 하나하나 고정하는 경우가 최악의 경우 N가지 있으므로 시간복잡도는 O(N^4)이고, 문제에서 주어진 N의 크기가 50이므로 문제를 해결할 수 있다. (글쓴이는 처음에 이게 통과 안될거라고 잘못 짐작하여 생각을 오래 했다...)

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

bool sieve[2000];

vector<int> oddnums, evennums;
vector<int> G[1001];
int matching[1001];
int visited[1001];
int fixednum;

int bipartite(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	if (current == fixednum) return 0;
	for (auto node : G[current]) {
		if (node == fixednum) continue;
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		else if (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	sieve[0] = sieve[1] = 1;
	for (int i = 2; i < 44; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 2000; j += i) {
			sieve[j] = 1;
		}
	}

	int N; cin >> N;
	int first; cin >> first;
	for (int i = 1; i < N; i++) {
		int x; cin >> x;
		if (x & 1) oddnums.emplace_back(x);
		else evennums.emplace_back(x);
	}

	for (auto o : oddnums) {
		for (auto e : evennums) {
			if (sieve[o + e]) continue;
			G[o].emplace_back(e);
		}
	}

	vector<int> ans;

	if (first & 1) {
		for (auto e : evennums) {
			if (sieve[first + e]) continue;
			memset(matching, 0, sizeof(matching));
			fixednum = e;
			int cnt = 0;
			for (auto o : oddnums) {
				memset(visited, 0, sizeof(visited));
				cnt += bipartite(o);
			}

			if (cnt + 1 == N / 2) ans.emplace_back(e);
		}
	}
	else {
		for (auto o : oddnums) {
			if (sieve[first + o]) continue;
			memset(matching, 0, sizeof(matching));
			fixednum = o;
			int cnt = 0;
			for (auto o : oddnums) {
				memset(visited, 0, sizeof(visited));
				cnt += bipartite(o);
			}

			if (cnt + 1 == N / 2) ans.emplace_back(o);
		}
	}

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

	if (ans.empty()) cout << -1;
	else {
		for (auto x : ans) cout << x << ' ';
	}
}