백준 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<<' ';
    }
}