백준 1017번 소수 쌍

문제 링크입니다: https://www.acmicpc.net/problem/1017

 

소수 관련된 문제이므로 에라토스테네스의 체와 이분 매칭을 통해 풀 수 있는 문제였습니다.

저도 처음에 백트래킹으로 접근했다가 TLE가 발생했던 문제입니다 ㅠ

 

알고리즘은 다음과 같습니다.

1. nums[0]과 합쳤을 때 소수를 이루는 nums[i]를 매칭합니다.

2. 남은 수들로 이분 그래프를 만드는데 왼쪽 집합은 홀수인 수들, 오른쪽 집합은 짝수인 수들로 구성하며 간선은 두 수의 합이 소수일 때 연결시킵니다.

3. 이분 그래프에서 최대 매칭을 찾아서 모든 노드가 매칭에 포함되는지 확인합니다.

3.1 매칭의 크기가 남은 노드의 절반이라면 모든 수를 짝지을 수 있다는 의미입니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <set>
	#include <cmath>
	#include <cstring>
	using namespace std;
	const int MAX_N = 50;
	const int MAX_NUM = 1000;
	const int MAX_SUM = 2000;
	int N;
	int nums[MAX_N];
	bool isPrime[MAX_SUM + 1];
	vector<int> graph[MAX_N];
	int match[MAX_N];
	bool visited[MAX_N];
	void eratosthenes()
	{
	fill(isPrime, isPrime + MAX_SUM + 1, true);
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i * i <= MAX_SUM; i++)
	{
	if (isPrime[i])
	{
	for (int j = i * i; j <= MAX_SUM; j += i)
	{
	isPrime[j] = false;
	}
	}
	}
	}
	bool func(int u)
	{
	for (int v : graph[u])
	{
	if (!visited[v])
	{
	visited[v] = true;
	if (match[v] == -1 || func(match[v]))
	{
	match[v] = u;
	return true;
	}
	}
	}
	return false;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	vector<int> odds, evens;
	for (int i = 0; i < N; i++)
	{
	cin >> nums[i];
	}
	eratosthenes();
	set<int> candidates;
	for (int i = 1; i < N; i++)
	{
	if (!isPrime[nums[0] + nums[i]])
	{
	continue;
	}
	// 첫 번째 수와 nums[i]를 짝으로 고정
	odds.clear();
	evens.clear();
	for (int j = 1; j < N; j++)
	{
	if (i == j)
	{
	continue;
	}
	nums[j] % 2 == 0 ? evens.push_back(j) : odds.push_back(j);
	}
	if (odds.size() != evens.size())
	{
	continue;
	}
	for (int j = 0; j < N; j++)
	{
	graph[j].clear();
	}
	// 간선 연결
	for (int u : odds)
	{
	for (int v : evens)
	{
	if (isPrime[nums[u] + nums[v]])
	{
	graph[u].push_back(v);
	}
	}
	}
	memset(match, -1, sizeof(match));
	int matchCount = 0;
	// 각 홀수 노드에 대해 매칭 시도
	for (int u : odds)
	{
	memset(visited, false, sizeof(visited));
	if (func(u))
	{
	matchCount++;
	}
	}
	if (matchCount == odds.size())
	{
	candidates.insert(nums[i]);
	}
	}
	if (candidates.empty())
	{
	cout << -1 << "\n";
	return 0;
	}
	for (int candidate : candidates)
	{
	cout << candidate << " ";
	}
	cout << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~