백준[1017] 소수 쌍

문제 설명

문제 링크

http://icpc.me/1017

1017번: 소수 쌍

풀이

이분 매칭과 에라토스테네스의 체를 이용하여 풀 수 있다.

우선 2000이하의 모든 소수를 에라토스테네스의 체를 이용하여 판별해놓는다.

그 후에 첫번째 수와 소수를 만들 수 있는 수 k를 하나 잡고 나머지 수들을 모두 소수 쌍으로 만들 수 있는 k들을 모두 구하면 된다. 나머지 수들을 모두 소수 쌍으로 만들 때 이분 매칭을 이용한다. 간선을 연결할 때는 소수 쌍을 이루는 간선들만 연결을 한다.

코드

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 2003;
bool prime[N];
int arr[N];
int visited[N];
int r[N];
int n;
vector<int> ret;

bool dfs(int x) {
    visited[x] = true;
    for (int i = 1; i < n; i++) {
        if (i == x || !prime[arr[x] + arr[i]]) continue;
    	// 자기 자신과 연결하거나, 소수가 아닌것을 연결하지 못하게 한다.        
        if (r[i] == -1 || (!visited[r[i]] && dfs(r[i]))) {
            r[i] = x;
            return true;
        }
    }
    return false;
}

int main() {
    memset(prime, true, sizeof prime);
    for (int i = 2; i * i < N; i++) {
        if (!prime[i]) continue;
        for (int j = i * i; j < N; j += i) prime[j] = false;
    }

    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    for (int i = 1; i < n; i++) {
    	// 첫번째 수와 소수쌍을 이루는 것만 검사한다.
        if (!prime[arr[0] + arr[i]]) continue;
        memset(r, -1, sizeof r);
        
        bool flag = true;
        for (int j = 1; j < n; j++) if (j != i) {
            memset(visited, false, sizeof visited);
            visited[i] = true;
            // 이분매칭을 실패하면 나머지 수들을 모두 소수쌍으로 만들 수 없다고 판단.
            if (!dfs(j)) flag = false;
        }
        if (flag) ret.push_back(arr[i]);
    }
    sort(ret.begin(), ret.end());
    if (ret.empty()) cout << "-1";
    else for (auto &k : ret) cout << k << " ";
}