[백준 1017] 소수 쌍

[ghdcksgml1]

아이디어

이건 이분 매칭 간선만드는 아이디어가 너무 어려웠다.

처음에는 소수가 되는 쌍을 모두 간선에 추가해 탐색하는 방식으로 했는데 실패했다. 그렇게 디버깅하다가 안되는다는 것을 깨닫고,

다른 방법으로 소수가 될 가능성이 있는 숫자에 생각해봤다.

1. 일단 짝수+짝수는 무조건 짝수니께 소수가 될수 없다. (X)
2. 짝수 + 홀수는 홀수니께 소수가 될 가능성이 있다! (O)
3. 홀수 + 홀수는 짝수니께 소수가 될 수 없다. (X)

따라서 각 쌍을 더한 값이 홀수가 나오도록 간선을 추가했고, 첫번째와 그에 매칭되는 두개의 간선은 고정해두고, 나머지 간선의 최대연결을 통해 답을 도출해냈다.

아래는 간선이 생기는 경우를 표시해봤다.

시간복잡도

O(VE)

소스코드

// 언어 : C++ , (성공/실패) : 1/2 , 메모리 : 2056 KB , 시간 : 12 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#define MAX 1001

using namespace std;

vector<int> a[MAX];
int d[MAX];
bool c[MAX];

vector<int> tmp;

bool pn[3001];
int isDone_1 = 0, isDone_2 = 0;
vector<int> result;

void era(){
    for(int i=2;i*i<=3000;i++){
        if(pn[i]) continue;
        for(int j=2;i*j<=3000;j++){
            pn[i*j] = true;
        }
    }
}

bool dfs(int x){
    if(x == isDone_1 || x == isDone_2) return false;
    for(auto t : a[x]){
        if(c[t]) continue;
        if(pn[x+t]) continue;
        c[t] = true;
        if(d[t]==-1 || dfs(d[t])){
            d[t] = x;
            return true;
        }
    }
    return false;
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    era();
    int N; cin>>N;
    for(int i=0;i<N;i++) {
        int t;cin>>t;
        tmp.push_back(t);
    }

    int size = tmp.size();
    vector<pair<int,int>> v;
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            if(tmp[i]+tmp[j] & 1){
                if(i==0) {
                    v.push_back({tmp[j],j});
                }
                else{
                    a[tmp[i]].push_back(tmp[j]);
                }
            }
        }
    }

    isDone_1 = tmp[0];
    for(int i=0;i<v.size();i++){
        fill(d,d+MAX,-1);
        isDone_2 = v[i].first;
        if(pn[isDone_1+isDone_2]) continue;

        int count = 0;
        d[isDone_1] = isDone_2;
        d[isDone_2] = isDone_1;
        for(int i=1;i<MAX;i++){
            fill(c,c+MAX,false);
            if(dfs(i)) {
                count++;
            }
        }

        if(N-2 == count) result.push_back(isDone_2);

    }
    sort(result.begin(), result.end());
    if(result.size()) {
        for (auto x: result) cout << x << ' ';
    }else{
        cout<<-1<<'\n';
    }

    return 0;
}

넘나 어려웡...

[BanApp]

소수라니 재밌어 보이네요 저도 한번 도전해보고 고통받고 오겠습니다!