1017번: 소수 쌍 
문제 링크: 1017번: 소수 쌍
개요
수의 리스트가 주어지면, 리스트에 있는 모든 수에 대해 두 수를 합해 소수가 되도록 짝을 지어줄 수 있는지 여부(A)를 확인해야 한다. 또한 첫 번째 수와 짝지었을 때 A가 되는 모든 수를 오름차순으로 출력해야 한다.
이 문제에서 주어진 리스트는 하나 뿐이지만 두 그룹으로 나누어서 짝을 지어주면 된다. 왜냐하면 서로 다른 두 자연수의 합으로 만들어지는 소수는 모두 홀수이기 때문이다. (가장 작은 케이스: 1 + 2 = 3)
따라서 주어지는 수를 홀수와 짝수로 구분해서 저장했다.
두 그룹으로 나눈 원소들에게 짝을 지어줄 땐 이분 매칭 알고리즘을 이용하면 된다. 이분 매칭 알고리즘에 대해 이분 매칭(Bipartite Matching)에 잘 나와있다.
풀이
eratosthenes 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
void eratosthenes(int n) {
for (int i = 2; i <= n; i++) {
isPrime[i] = 1;
}
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = 0;
}
}
}
}
평범한 에라토스테네스의 체이다. 이에 대해 22. 에라토스테네스의 체에 잘 나와있다. 범위 내의 모든 수를 빠르게 미리 소수 판정을 해서 isPrime 배열에 저장해주는 함수이다.
리스트에 들어있는 수는 1000보다 작거나 같은 자연수라고 나와있으므로, 리스트의 두 수를 합했을 때의 최댓값인 2000까지 판정해두면 된다. main함수에서 eratosthenes(2000)을 1회 호출해서 소수 판정을 해두고, 이후 n의 소수 여부를 확인할 때 isPrime[n]를 참조했다.
입력받기
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
if (i == 0) firstNum = num;
if ((num + firstNum) % 2 == 0) arr1[cnt1++] = num;
else arr2[cnt2++] = num;
}
if (cnt1 != cnt2) {
printf("-1");
return 0;
}
개요에서 말한 대로 2로 나눴을 때의 나머지가 첫 번째로 주어지는 수와 같은 수는 arr1에, 다른 수는 arr2에 입력했다. cnt1과 cnt2는 각 배열 원소의 수인데, 모든 수를 입력받은 시점에서 cnt1과 cnt2가 서로 다를 경우 절대로 모든 수에 대해 짝을 지어줄 수 없기 때문에 -1을 출력하고 바로 프로그램을 종료했다.
정답 구하기
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
bool vstd[MAX_N] = { false };
int pairIdx[MAX_N] = { 0 };
int ans[MAX_N], ansIdx = 0;
for (int firstPairIdx = 0; firstPairIdx < cnt2; firstPairIdx++) {
if (isPrime[arr1[0] + arr2[firstPairIdx]]) {
int cnt = 1;
for (int toIdx = 0; toIdx < cnt2; toIdx++) pairIdx[toIdx] = -1;
pairIdx[firstPairIdx] = 0;
vstd[0] = true;
for (int fromIdx = 1; fromIdx < cnt1; fromIdx++) {
for (int i = 1; i < cnt1; i++) vstd[i] = false;
if (dfs(fromIdx)) cnt++;
}
if (cnt == n / 2) {
ans[ansIdx++] = arr2[firstPairIdx];
}
}
}
ans는 우리가 최종 출력할 값인, ‘첫 번째 수와 짝지었을 때 모든 수를 짝지을 수 있게 되는 수’들을 담을 배열이다. 오름차순으로 출력해야 하기 때문에 바로 출력하지 않고 배열에 보관했다가 이후 정렬해서 출력하면 된다.
arr2 배열의 모든 원소에 대해 확인하면서(firstPairIdx가 도는 반복문) arr1[0]에 짝을 지어주고, arr1[0]을 제외한 arr1 배열의 모든 원소에 대해(fromIdx가 도는 반복문) dfs()를 호출해 짝을 지어줄 수 있는지 이분 매칭 알고리즘을 확인했다. 지어진 짝의 개수(cnt)가 리스트의 수의 개수의 절반이라면 모든 수가 짝지어진 것이므로 firstPairIdx를 ans 배열에 추가했다.
vstd 배열은 arr1의 어떤 원소에 해당하는 인덱스를 이미 방문했는지 표시하는 배열로, 매 dfs()를 호출하기 전마다 false로 초기화했다. 즉 이번 탐색(main에서의 dfs() 호출)에서 이미 지나온 원소로 또 진입하는 걸 막기 위함이다. pairIdx배열은 arr2의 특정 인덱스에 해당하는 원소가 arr1의 어떤 인덱스에 매칭된 원소인지 저장하는 배열이다. arr1[0]에 매칭시킨 원소가 바뀔 때마다-1로 초기화했다.
dfs 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool vstd[MAX_N] = { false };
int pairIdx[MAX_N] = { 0 };
int dfs(int fromIdx) {
vstd[fromIdx] = true;
for (int toIdx = 0; toIdx < cnt2; toIdx++) {
if (isPrime[arr1[fromIdx] + arr2[toIdx]]) {
if (pairIdx[toIdx] == -1 || !vstd[pairIdx[toIdx]] && dfs(pairIdx[toIdx])) {
pairIdx[toIdx] = fromIdx;
return 1;
}
}
}
return 0;
}
fromIdx는 arr1에 해당하는 인덱스이고, toIdx는 arr2에 해당하는 인덱스이다.
arr2에 해당하는 인덱스에 해당하는 원소(arr2[toIdx])를 모두 탐색해 해당 인덱스의 원소가 매칭되지 않았거나, arr2[toIdx]의 매칭 상대(pairIdx[toIdx])의 상대를 바꿀 수 있다면 바꾼 뒤 (이 과정에서 재귀 호출이 발생하고, 바꿀 수 있는 경우엔 바뀐 후에 현재 재귀 스택으로 돌아와 다음 작업을 진행하게 된다.) pairIdx에 해당하는 원소에 arr2[toIdx]를 매칭시켜준다.
매칭 성공 시 1을 바로 반환하고, arr2의 모든 원소와도 매칭이 불가능할 경우 0을 반환한다.
전체 코드
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
#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 50
#define MAX_NUM 1000
bool isPrime[MAX_NUM * 2 + 1] = { 0 };
bool vstd[MAX_N] = { false };
int pairIdx[MAX_N] = { 0 };
int arr1[MAX_N], arr2[MAX_N], cnt1 = 0, cnt2 = 0;
void eratosthenes(int n);
int dfs(int from);
int main() {
int n, firstNum;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
if (i == 0) firstNum = num;
if ((num + firstNum) % 2 == 0) arr1[cnt1++] = num;
else arr2[cnt2++] = num;
}
if (cnt1 != cnt2) {
printf("-1");
return 0;
}
eratosthenes(MAX_NUM * 2);
int ans[MAX_N], ansIdx = 0;
for (int firstPairIdx = 0; firstPairIdx < cnt2; firstPairIdx++) {
if (isPrime[arr1[0] + arr2[firstPairIdx]]) {
int cnt = 1;
for (int toIdx = 0; toIdx < cnt2; toIdx++) pairIdx[toIdx] = -1;
pairIdx[firstPairIdx] = 0;
vstd[0] = true;
for (int fromIdx = 1; fromIdx < cnt1; fromIdx++) {
for (int i = 1; i < cnt1; i++) vstd[i] = false;
if (dfs(fromIdx)) cnt++;
}
if (cnt == n / 2) {
ans[ansIdx++] = arr2[firstPairIdx];
}
}
}
sort(ans, ans + ansIdx);
for (int i = 0; i < ansIdx; i++) {
printf("%d ", ans[i]);
}
if (ansIdx == 0) printf("-1");
return 0;
}
void eratosthenes(int n) {
for (int i = 2; i <= n; i++) {
isPrime[i] = 1;
}
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = 0;
}
}
}
}
int dfs(int fromIdx) {
vstd[fromIdx] = true;
for (int toIdx = 0; toIdx < cnt2; toIdx++) {
if (isPrime[arr1[fromIdx] + arr2[toIdx]]) {
if (pairIdx[toIdx] == -1 || !vstd[pairIdx[toIdx]] && dfs(pairIdx[toIdx])) {
pairIdx[toIdx] = fromIdx;
return 1;
}
}
}
return 0;
}