BOJ 1017(소수 쌍) 풀이

이분 매칭 문제입니다.

 

solved.ac 티어 : 플래티넘 3

www.acmicpc.net/problem/1017

1017번: 소수 쌍

이문제는 입력받은 것을 2중 반복하면서 자신이랑 위치가 다른 곳 중에서 둘이 더했을 때 소수일 때만 배열에 넣어주고

배열에서 첫 번째 위치의 배열에 들어있는 수 개수만큼 반복하면서 첫 번째 수랑 더했을 때 소수가 되는 수들이랑 첫 번째 수를 하나하나 빼면서 나머지 수들로 전부다 짝이 만들어질 경우 배열에 넣고 마지막에 정렬해서 출력하면 된다.

 

이문제는 설명만 보기보단 코드를 같이 보면서 이해하는 게 더 좋을 거 같다.(베끼지는 맙시다)

 

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll inf=1e9;
vector<ll> l[2005],rt;
ll t[2005],q[1001],y[100];
ll prime(ll x){ //소수인지 판별하는코드
    for(int j=2;j*j<=x;j++){
        if(x%j==0){return 0;}
    }
    return 1;
}
bool dfs(ll x,ll n1,ll n2){  // 이분매칭코드
    if(x==n1||x==n2){return false;}
    for(int i=0;i<l[x].size();i++){
        ll y=l[x][i];
        if(y==n1||y==n2){continue;}
        if(t[y]){continue;}
        t[y]=true;
        if(q[y]==0||dfs(q[y],n1,n2)){
            q[y]=x;
            return true;
        }
    }
    return false;
}
int main()
{
    ll n,m,c,d,cnt=0,r=0,o=0,k,u=0,qt=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&y[i]);
    }
    for(int i=1;i<=n;i++){//반복하면서 자신을 제외한 다른수랑 더했을때 소수인지 판별해서 소수이면 배열에 넣는 코드
        for(int g=1;g<=n;g++){
            if(i!=g){
                ll o=prime(y[i]+y[g]);
                if(o==1){
                    l[i].push_back(g);
                }
            }
        }
    }
    for(int g=0;g<l[1].size();g++){//첫번재값과 더했을때 소수가 되는 수개수만큼 반복하면서 나머지숫자들이 전부다 짝이 있는지 구하는코드
        fill(q,q+1001,0);
        cnt=0;
        for(int i=1;i<=n;i++){
            fill(t,t+1001,false);
            if(dfs(i,1,l[1][g])){cnt++;}
        }
        
        if(cnt==n-2){ //첫번째 값과 첫번째값과 더했을때 소수가 되는 g번째수 2개를 뺐을때 나머지 수들이 짝이 맞는지 안맞는지 판별 후 배열에 넣기
            rt.push_back(y[l[1][g]]);
            qt++;
            //printf("%lld\n",y[l[1][g]]);
        }
    }
    if(qt==0){printf("-1");}
    else{
        sort(rt.begin(),rt.end());  //배열에 넣은값들을 정렬해서 출력
        for(int i=0;i<qt;i++){
            printf("%lld ",rt[i]);
        }
    }
    
            
}