Algorithm_2023/boj1017 at main · YEJIRYOO/Algorithm_2023 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 2001;
bool is_prime[MAXN+1];
int arr_size;
vector<int> a_set, b_set;
vector<vector<int>> adj;
vector<int> a_match, b_match, visited;

void SieveEratos(){
  memset(is_prime, true, sizeof(is_prime));
  int sqrtn = int(sqrt(MAXN));

  is_prime[0] = is_prime[1] = false;
  for(int i=2; i<=sqrtn ; ++i){
    if(is_prime[i])
      for(int j= i*i ; j<=MAXN ; j+= i)
        is_prime[j] = false;
  }
}

bool DFS(int a_idx){
  //a가 첫번째 수라면 이미 다른 수와 연결되어 있음
  if(a_idx == 0 || visited[a_idx])
    return false;
  visited[a_idx] = true;

  for(int i=0; i<adj[a_idx].size() ; ++i){
    int b_idx = adj[a_idx][i];

    if(b_match[b_idx] == -1 || DFS(b_match[b_idx])){
      a_match[a_idx] = b_idx;
      b_match[b_idx] = a_idx;
      return true;
    }
  }

  return false;
}


int main(){
  ios_base::sync_with_stdio(0);
  cin>>arr_size;

  int first_num;
  cin>>first_num;

  bool is_first_even;
  is_first_even = first_num%2 ==0 ? true : false;
  a_set.push_back(first_num);

  int temp;
  for(int i=1; i<arr_size ; ++i){
    cin>>temp;

    //첫수가 짝수라면 a집합은 짝수의 집합
    if(is_first_even){
      if(temp %2 == 0)
        a_set.push_back(temp);
      else
        b_set.push_back(temp);
    //첫수가 수라면 a집합은 홀수의 집합
    }else{
      if(temp %2 != 0)
        a_set.push_back(temp);
      else
        b_set.push_back(temp);
    }
  }

  //애초에 짝수와 홀수의 개수가 맞지 않는 경우
  if(b_set.size() != a_set.size()){
    cout<<-1<<'\n';
    return 0;
  }

  //에라토스테네스의 체
  SieveEratos();

  //a 집합의 수들과 소수를 이루는 b 집합의 수를 연결
  adj = vector<vector<int>>(a_set.size());
  for(int i=0; i<a_set.size() ; ++i)
    for(int j=0; j<b_set.size() ; ++j)
      if(is_prime[a_set[i]+b_set[j]])
        adj[i].push_back(j);


  vector<int> answers;
  for(int i=0; i<adj[0].size(); ++i){
    int pair_b_idx = adj[0][i];
    int paired_size =1;

    a_match = vector<int>(a_set.size(), -1);
    b_match = vector<int>(b_set.size(), -1);

    //첫번째 수와 미리 연결해주자.
    a_match[0] = pair_b_idx;
    b_match[pair_b_idx] = 0;

    for(int j =1 ; j<a_set.size() ; ++j){
      visited = vector<int>(a_set.size(), false);
      if(DFS(j))
        paired_size++;
    }

    if(paired_size == b_set.size())
      answers.push_back(b_set[pair_b_idx]);
  }

  if(answers.size() != 0){
    sort(answers.begin(), answers.end());
    for(int i=0; i<answers.size() ; ++i)
      cout<<answers[i]<<' ';
  }else
    cout<<-1;

  cout<<'\n';

  return 0;
}