백준 1017번 - 소수 쌍

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

1017번: 소수 쌍

필요한 배경지식

• 이분매칭
• 소수판정 - (에라토스테네스의 체)

 

 

문제 해결 방법

 

이분매칭을 이용하면 됩니다.

 

우선 두 수를 더한 값이 소수일때 두 수를 연결하는 간선을 추가하여 그래프를 만들어야 합니다.

그 다음 이분매칭을 하여 매칭된 쌍의 개수가 N/2개일때 첫 번째 수와 짝지어진 수를 출력하면 됩니다.

 

소수를 판정할 때에는 두 수를 더한 값이 최대 2000이기 때문에 에라토스테네스의 체를 이용하여

전처리 후 소수를 판정했습니다.

 

이분매칭할때 주의할 점은 한 집단 내에서 매칭을 해야하기 때문에 매칭할때 간선을 양쪽으로 확인해 주어야 합니다.

(예를들어 양방향으로 확인하지 않으면, 1과 4가 매칭되었는데 4와 7이 매칭되어 4가 한번 더 매칭될 수 있음)

 

또한, 첫번째 수와 짝지어진 수를 확인해야 하기 때문에 첫 번째 수를 포함하여 미리 한 쌍을 매칭해 주고 매칭된 쌍의 총 개수가 N/2개인지 확인해 주어야 합니다.

 

 

 

 

 

전체 코드

#include<bits/stdc++.h>
#define MAX 2000
using namespace std;

int N;
int arr[50]{};
int sieve[MAX+1];
vector<int> adj[51]{};
int A[51]{};
int B[51]{};
bool vi[51]{};

void find_prime(){
​​​​memset(sieve, -1, sizeof(sieve));
​​​​for(int i=2; i*i<=MAX; ++i)
​​​​​​​​if(sieve[i] == -1)
​​​​​​​​​​​​for(int j=i*i; j<=MAX; j+=i)
​​​​​​​​​​​​​​​​if(sieve[j] == -1)
​​​​​​​​​​​​​​​​​​​​sieve[j] = i;
}

bool dfs(int cur){
​​​​if(vi[cur]) return false;
​​​​vi[cur] = true;
​​​​for(auto next : adj[cur]){
​​​​​​​​if(B[next]==-1 || dfs(B[next])){
​​​​​​​​​​​​A[cur] = next;
​​​​​​​​​​​​B[next] = cur;
​​​​​​​​​​​​A[next] = cur; // 양쪽으로 간선 확인
​​​​​​​​​​​​B[cur] = next; 
​​​​​​​​​​​​return true;
​​​​​​​​}
​​​​}
​​​​return false;
}

int main() {
​​​​ios_base::sync_with_stdio(0);
​​​​cin.tie(0);
​​​​find_prime();
​​​​cin>>N;
​​​​int t;
​​​​for(int i=0; i<N; i++) {
​​​​​​​​cin>>arr[i];
​​​​}
​​​​for(int i=0; i<N; i++){
​​​​​​​​for(int j=i+1; j<N; j++){
​​​​​​​​​​​​if(sieve[arr[i]+arr[j]]==-1) {
​​​​​​​​​​​​​​​​adj[i].push_back(j);
​​​​​​​​​​​​​​​​adj[j].push_back(i);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​vector<int> ans;
​​​​for(auto next : adj[0]){
​​​​​​​​memset(A, -1, sizeof(A));
​​​​​​​​memset(B, -1, sizeof(B));
​​​​​​​​int res = 1;
​​​​​​​​// 미리 한쌍 매칭
​​​​​​​​A[0] = next;
​​​​​​​​B[next] = 0;
​​​​​​​​A[next] = 0; // 양쪽으로 간선 확인
​​​​​​​​B[0] = next;
​​​​​​​​for(int i=1; i<N; i++){
​​​​​​​​​​​​if(A[i]==-1){
​​​​​​​​​​​​​​​​memset(vi, 0, sizeof(vi));
​​​​​​​​​​​​​​​​vi[0] = true;
​​​​​​​​​​​​​​​​vi[next] = true;
​​​​​​​​​​​​​​​​if(dfs(i)) res++;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(res==N/2) ans.push_back(arr[next]);
​​​​}
​​​​if(ans.size()==0) cout<<-1;
​​​​else {
​​​​​​​​sort(ans.begin(), ans.end());
​​​​​​​​for(auto val : ans) cout<<val<<' ';
​​​​}
}