1017 - 소수 쌍
본문
지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, $\lbrace 1, 4, 7, 10, 11, 12 \rbrace$가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다.
$1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23$
또는
$1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23$
수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 $1 + 12 = 13$으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 위의 경우 정답은 $4, 10$이다.
입력
첫째 줄에 리스트의 크기 $N$이 주어진다. $N$은 $50$보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 $1000$보다 작거나 같은 자연수이며, 중복되지 않는다.
출력
첫째 줄에 정답을 출력한다. 없으면 $-1$을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- $2 \leq N \leq 50$
- $1 \leq X_i \leq 1000$
풀이
문제가 짧고 간단하다. 문제에서 원하는 바도 명확하다. 그래서 문제 풀이도 간단하다고 생각했다. 그러나 현실은 그게 아니었다.
문제에서 원하는 것은 ‘모든 수가 2개씩 쌍을 이루어 더했을 때 모두 소수’가 되도록 하는 경우이다. 원소의 개수 $N$이 작으므로, 모든 경우에 대하여 쌍을 이루도록 하고 그것을 계산하면 될 것 같다. 그런데 이 경우를 시간복잡도로 계산하면 $\Pi {(2k-1)}$이다. $N$이 50이라면 대충 계산해도 $20!$은 족히 넘을텐데, 이것부터 시간제한을 초과해버린다. 그래서 그냥 모든 쌍을 구해보는 방법으로는 구현할 수 없다.
한동안 포기했던 문제인데, 최근에 이분 매칭이라는 방법에 대해 들어보게 되었다. 이분 매칭 방법은 “정점들을 2개의 그룹으로 완벽하게 나눌 수 있다면 만들 수 있는 pair의 최대 개수를 반환”하는 알고리즘이다. 이분 매칭에 대해 공부하고 나서 이 문제를 다시 보니 실마리가 보이기 시작했다.
먼저, 이분 매칭을 적용할 수 있는지 확인해야한다. 조건은 “정점들을 2개의 그룹으로 완벽하게 분할할 수 있는가?”이다. 우선 입력으로 주어지는 숫자는 짝수개이며 중복이 없다고 한다. 문제에서는 쌍을 이루었을 때, 그것을 더해서 소수인 쌍을 원한다. 소수는 $2$를 제외하고는 모두 홀수이다. 그런데, $2$를 만들기 위해서는 2개의 자연수를 더하는 방법으로는 $1+1=2$밖에 존재하지 않는다. 그런데 입력으로 주어지는 숫자들은 중복이 없다고 하였으므로 $2$를 만들 수 있는 방법은 없다. 그래서 이 문제에서는 구하려는 소수들은 모두 홀수라고 가정하고 진행할 수 있다. 2개의 수를 더할 경우, 홀수를 만들기 위해서는 항상 $\text{홀수} + \text{짝수} = \text{홀수}$이어야한다. 즉, 쌍을 이루는 숫자들은 항상 하나는 홀수, 다른 하나는 짝수이어야 한다는 조건을 만들 수 있다. 이 조건은 서로 겹칠 수 없으므로, 정점을 2개의 그룹으로 완벽하게 분할할 수 있다. 그러면 이분 매칭을 적용할 수 있는 문제로 바뀐다!
적용할 수 있다는 것을 알았으니 실행에 옮기자. 설계는 아래와 같이 진행하였다.
- 정점을 2개 그룹으로 분할한다. 이 문제에서는 정점을 “홀수 / 짝수” 로 분할한다면 완벽하게 분할할 수 있다
- 이 2개 그룹의 원소 개수는 같아야한다. 그렇지 않으면 쌍을 이루는 원소가 한 쪽이 부족해진다
- 그래프를 만들기 위한 간선을 지정해주어야한다. 이 때 간선은 유망한 것들로 만들어야한다
- 유망한 간선은, 간선 상에 존재하는 2개의 정점의 합이 소수인 경우로 지정할 수 있다
이렇게 이분 매칭 초기상태를 설정하고 알고리즘을 진행하면 된다. 다만 문제에서 원하는 것이 매칭 최대 개수가 아니라, “모든 쌍을 매칭할 수 있을 때, 첫번째 원소와 매칭되는 원소를 모두 출력“하라는 것이다. 결국 매칭의 개수가 $\frac{N}{2}$인 경우, 첫번째 원소와 매칭된 원소를 모두 출력하라는 문제이다. 이것은 구해보기 전까지는 모르므로, 첫번째 원소와 다른 노드를 강제로 쌍을 이룬 이후 다른 노드들끼리 매칭을 시도하자. 이 때 만들어진 매칭 개수가 $\frac{N}{2}$라면 첫번째 원소와 매칭된 노드는 답으로 출력할 수 있다. 만약 이런 노드가 하나도 없다면 문제에서 원하는 정답이 없다고 판단할 수 있을 것이다.
- 참고 알고리즘 : 이분 매칭
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 24
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX 25
#define MAX_VAL 1000
#define START 0
#define NONMATCHED -1
bool isNotPrime[MAX_VAL * 2 + 1];
void primeInit() {
isNotPrime[0] = isNotPrime[1] = true;
for (int i = 2; i <= MAX_VAL * 2; ++i) {
if (isNotPrime[i] == false) {
for (int j = i * 2; j <= MAX_VAL * 2; j += i) {
isNotPrime[j] = true;
}
}
}
return;
}
int arr[2][MAX_IDX * 2]; // odd or even
int len[2];
int n;
bool visit[MAX_IDX];
int matched[MAX_IDX];
int cmp(int* a, int* b) {
return *a > *b;
}
bool matrix[MAX_IDX][MAX_IDX];
bool dfs(int x) {
for (int i = 0; i < len[1]; ++i) {
if (matrix[x][i] == true) {
if (visit[i] == true) {
continue;
}
visit[i] = true;
if (matched[i] == NONMATCHED || dfs(matched[i]) == true) {
matched[i] = x;
return true;
}
}
}
return false;
}
int main() {
primeInit();
scanf("%d", &n);
scanf("%d", &arr[0][START]);
len[0] = 1, len[1] = 0;
for (int i = 1; i < n; ++i) {
int a;
scanf("%d", &a);
bool temp = (((a + arr[0][START]) % 2) == 1);
arr[temp][len[temp]++] = a;
}
if (len[0] != len[1]) { // first exit case
printf("-1");
return 0;
}
qsort(arr[1], len[1], sizeof(int), cmp);
for (int i = 1; i < len[0]; ++i) { // except the first element
for (int j = 0; j < len[1]; ++j) {
matrix[i][j] = (isNotPrime[arr[0][i] + arr[1][j]] == false);
}
}
bool isAnswerExists = false;
// search for all node in arr[1][]
for (int i = 0; i < len[1]; ++i) {
if (isNotPrime[arr[0][START] + arr[1][i]] == false) {
matrix[START][i] = true;
for (int j = 0; j < len[1]; ++j) {
matched[j] = NONMATCHED;
}
// bipartite matching algorithm
int matchCount = 0;
for (int j = 0; j < len[1]; ++j) {
for (int k = 0; k < len[1]; ++k) {
visit[k] = false;
}
if (dfs(j) == true) {
++matchCount;
}
}
if (matchCount == len[1]) {
isAnswerExists = true;
printf("%d ", arr[1][i]);
}
matrix[START][i] = false;
}
}
if (isAnswerExists == false) {
printf("-1");
}
return 0;
}
isNotPrime[]: 원소가 소수인지 아닌지 기록한 배열.false를 가지는 것이 소수임에 유의할 것arr[2][]: 입력받은 숫자를 2개의 그룹으로 분할하기 위해 2차원 배열로 지정하였음. 분할 조건은 홀짝arr[0][]: 첫번째 원소와 같은 성질,arr[1][]: 첫번째 원소와 다른 성질- 각 배열에 있는 원소 개수는
len[2]로 기록
matrix[][]: 간선의 정보를 인접행렬로 기록. 때에 따라 인접리스트로도 구현할 수 있음