소수 쌍

---

🔗 🔗 전체 1017번 문제

조건

---

문제

---

지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, ${1, 4, 7, 10, 11, 12}$가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다.

$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보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

출력

---

첫째 줄에 정답을 출력한다. 없으면 -1을 출력한다.

케이스

---

예제 1

---

• 입력

TC
1
2
6
1 4 7 10 11 12

• 출력

TC
1
4 10

풀이

---

🔗 1014번 컨닝문제를 통해 이분 매칭을 접한 덕분인지, 지금까지 푼 플래티넘 중에서는 그나마 좀 이해되는 문제였다.

역시 내용이 다소 난해한데, 알고리즘이 요구하는 동작은 다음과 같이 정리할 수 있다. 입력된 6개의 숫자 배열 ${ 1, 4, 7, 10, 11, 12 }$이 있다고 가정하자. 배열의 숫자를 한 쌍씩 짝지어 더하면 총 3개의 수가 나온다. 이렇게 짝지어 더한 수가 모두 소수일 경우, 입력의 첫 번째 숫자와 매칭된 숫자들을 오름차순으로 정렬하여 출력하는 문제다.

예제에서도 설명해주듯이, 짝지은 수가 모두 소수인 경우는 $1 + 4 = 5$, $7 + 10 = 17$, $11 + 12 = 23$과 $1 + 10 = 11$, $4 + 7 = 11$, $11 + 12 = 23$가 된다. 입력의 가장 첫 번째 숫자가 1이므로, 1와 매칭된 4, 10이 정답이 된다.

소수 판별하기🍳

---

이제 좀 더 세부적인 내용을 살펴보자. 문제 해결의 핵심은 소수다. 이 알고리즘에선 소수 판별이 필요하다. 많은 판별방법이 있지만, 가장 대표적인 에라토스 테네스의 체를 활용하면 어렵지 않게 해결할 수 있다.

요소 한 쌍씩 그룹화하기

---

소수 판별 방법도 마련했겠다, 입력된 숫자 배열을 적절히 짝지어야한다. 핵심은 짝지은 수의 합이 소수가 되는 것. 요소를 한번씩 다 더해보는 방법도 있겠지만, 배열의 크기가 커질 수록 요구되는 연산량 또한 높아지므로 적절하지 않다. 즉, 가능성 있는 조합으로만 그룹화해야한다.

소수에 대해 생각해보자. 소수는 1과 자기 자신으로만 나눠지는 수다. 즉, 반드시 소수는 홀수여야 한다. 이 전제를 확장하면 짝지은 수의 합이 홀수여야한다. 두 수를 더했을 때 홀수가 나오는 경우는 홀수 + 짝수로 한 가지 경우의 수만 존재한다.

따라서 우리는 입력값을 홀수와 짝수 그룹으로 나누어 각 그룹끼리만 더하면 결과는 모두 홀수일 것이므로, 해당 수는 소수일 가능성이 있다. 두 개의 그룹을 겹치지 않게 조합해야하므로 이분 매칭이 적절한 해답이 될 수 있다. 각 그룹은 홀수와 짝수로 나누고, 더했을 때 소수가 되는 쌍을 노드로 연결하면 이분 매칭으로 접근 가능하다.

위 그림은 예제 1을 홀수와 짝수 그룹으로 나눠 이분매칭으로 표시한 그림이다. 위 숫자를 6개의 숫자를 매칭하면 3개의 노드가 나올 것이다. 각 숫자를 더하기 위해선 반드시 하나의 쌍을 이뤄야하므로, 이분 매칭의 결과는 반드시 $N \div 2$가 되어야 한다.

예제의 가장 첫 번째 수는 1이다. 즉, 우리는 모든 요소쌍의 합이 모두 소수가 되는 조합을 찾고 해당 조합들에서 각각 1과 매칭되는 숫자를 구해야한다. 이를 확장시키면, 1과 짝을 이루는 수를 더한 값이 소수가 아닐 경우 애초에 비교할 필요가 없다.

위 그림의 매칭 결과가 3이 나온다면, 모든 요소를 적절히 짝지어 더한 값이 모두 소수가 되는 조합이 있다는 뜻이다. 해당 조합을 저장하여 1과 짝지은 값을 찾으면 될 것이다.
만약, 홀수와 짝수의 갯수가 일치하지 않을 경우, 매칭이 불가능하므로 문제에 제시한 조건에 따라 -1을 반환해야 한다.

1과 더했을 때 소수가 되는 요소는 4, 10, 12 모두 해당하므로 이를 모두 노드로 연결할 수 있다. 1과 매칭 가능한 요소 중 하나를 연결하면, 나머지 4개 요소에 대해서만 이분 매칭을 진행할 수 있다.

만약, 1과 4를 매칭했다면 나머지 4개 요소에 대한 소수 매칭은 그림과 같이 표현할 수 있다. $[ 7, 10 ]$, $[ 11, 12 ]$ 조합의 합이 모두 소수이므로, $[ 1, 4 ]$, $[ 7, 10 ]$, $[ 11, 12 ]$ 조합은 알고리즘의 조건에 부합한다. 따라서 4는 정답에 포함된다.

만약, 1과 12가 매칭된다면 어떨까? 이는 위 그림과 같이 표시할 수 있다. 7의 경우 4와 10 중 어떤걸 조합해도 소수지만, 11의 경우 4와 10 모두 소수가 아니므로 어떤식으로 매칭해도 4개 요소의 매칭 결과는 1이 된다. 즉, 1과 매칭된 조합 하나를 더한 최종 매칭 수는 2이므로 $N / 2$의 값에 부합하지 않으므로 해당 조합은 정답이 될 수 없다.
따라서 예제의 결과는 출력과 같이 4 10이 된다.

전체 소스

---

JAVA
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 백준 전체 1017 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1017">1017 풀이</a>
 * @since 2021.06.26 Sat 03:19:32
 */
public class Main
{
	// 에라토스 테네스의 체 배열 (소수 판별용)
	private static final boolean[] IS_NOT_PRIME = eratosthenes();
	
	// 왼쪽 배열 (이분매칭의 기준)
	private static int[] left;
	
	// 오른쪽 배열
	private static int[] right;
	
	// 노드 연결 여부
	private static boolean[][] hasNode;
	
	// 방문 여부
	private static boolean[] isVisit;
	
	// 매칭된 수
	private static int[] matched;
	
	// 현재 선택 중인 수
	private static int selected;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 입력값 갯수
		int N = Integer.parseInt(reader.readLine());
		
		// 입력값 배열
		int[] numbers = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		// 첫 번째 수가 홀수일 경우
		if (numbers[0] % 2 != 0)
		{
			// 왼쪽 배열에 홀수를 할당
			left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
			right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
		}
		
		// 첫 번째 수가 짝수일 경우
		else
		{
			// 왼쪽 배열에 짝수를 할당
			left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
			right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
		}
		
		// 홀수 배열과 짝수 배열의 수가 동일할 경우 (이분매칭 가능)
		if (left.length == right.length)
		{
			hasNode = new boolean[left.length][right.length];
			
			// left의 첫 번째 행은 기준 매칭이므로 이분 매칭에서 제외한다.
			for (int i = 1; i < left.length; i++)
			{
				for (int j = 0; j < right.length; j++)
				{
					int ref = left[i] + right[j];
					
					// left[i] + right[j]의 값이 소수일 경우
					if (!IS_NOT_PRIME[ref])
					{
						// 노드를 연결한다.
						hasNode[i][j] = true;
					}
				}
			}
			
			LinkedList<Integer> list = new LinkedList<>();
			
			// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
			for (int i = 0; i < N / 2; i++)
			{
				// left[0]와 right[i]의 합이 소수일 경우
				if (!IS_NOT_PRIME[left[0] + right[i]])
				{
					selected = i;
					
					int size = bipartite();
					
					// 모든 요소가 매칭될 경우
					if (size == N / 2)
					{
						list.add(right[selected]);
					}
				}
			}
			
			// 하나도 매칭되지 않은 경우
			if (list.size() == 0)
			{
				writer.write("-1");
			}
			
			// 매칭이 하나 이상 있을 경우
			else
			{
				// 오름차순으로 정렬
				list.sort(Integer::compareTo);
				
				StringBuilder builder = new StringBuilder();
				
				for (int item : list)
				{
					builder.append(item).append(" ");
				}
				
				writer.write(builder.toString().trim());
			}
		}
		
		// 홀수 배열과 짝수 배열의 수가 동일하지 않을 경우 (이분매칭 불가능)
		else
		{
			writer.write("-1");
		}
		
		writer.newLine();
		writer.close();
		reader.close();
	}
	
	/**
	 * 이분 매칭 갯수 반환 함수
	 *
	 * @return [int] 이분 매칭 갯수
	 */
	private static int bipartite()
	{
		// 이미 left[0]과 right 요소 하나가 선택됨
		int size = 1;
		
		matched = new int[left.length];
		
		Arrays.fill(matched, -1);
		
		for (int i = 1; i < left.length; i++)
		{
			isVisit = new boolean[left.length];
			
			// 매칭 가능할 경우
			if (dfs(i))
			{
				size++;
			}
		}
		
		return size;
	}
	
	/**
	 * DFS 알고리즘 결과 반환 함수
	 *
	 * @param num: [int] 시작점
	 *
	 * @return [int] 매칭 갯수
	 */
	private static boolean dfs(int num)
	{
		// 첫 방문일 경우
		if (!isVisit[num])
		{
			isVisit[num] = true;
			
			for (int i = 0; i < right.length; i++)
			{
				// 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
				if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
				{
					// 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
					if (matched[i] == -1 || dfs(matched[i]))
					{
						matched[i] = num;
						
						return true;
					}
				}
			}
		}
		
		return false;
	}
	
	/**
	 * 아레토스 테네스의 체 배열 반환 함수
	 *
	 * @return [boolean[]] 아레토스 테네스의 체
	 */
	private static boolean[] eratosthenes()
	{
		boolean[] isNotPrime = new boolean[2000];
		
		isNotPrime[0] = true;
		isNotPrime[1] = true;
		
		int maxPrime = (int) Math.ceil(Math.sqrt(2000));
		
		for (int i = 2; i < maxPrime; i++)
		{
			// 소수일 경우
			if (!isNotPrime[i])
			{
				for (int j = i + i; j < isNotPrime.length; j += i)
				{
					// 아직 소수가 아님을 표시하지 않았을 경우
					if (!isNotPrime[j])
					{
						// 소수의 배수는 소수가 아니므로 제외함
						isNotPrime[j] = true;
					}
				}
			}
		}
		
		return isNotPrime;
	}
}

편의상 항상 왼쪽을 기준으로 매칭한다. 올바른 조합 중 첫 번째 수와 매칭되는 수를 찾는 것이 목표인데, 첫 번째 수는 홀수, 짝수 모두 올 수 있다. 따라서 홀수가 먼저오냐, 짝수가 먼저오냐에 따라 해당하는 분류를 기준 배열로 할당한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 첫 번째 수가 홀수일 경우
if (numbers[0] % 2 != 0)
{
	// 왼쪽 배열에 홀수를 할당
	left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
	right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
}

// 첫 번째 수가 짝수일 경우
else
{
	// 왼쪽 배열에 짝수를 할당
	left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
	right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
}

해당 소스는 위와 같다. 왼쪽 배열 left를 기준으로하여 홀수가 올 경우 left에 홀수 배열을, 아닐 경우 짝수 배열을 할당한다.

소수 판별은 에라토스 테네스의 체 알고리즘을 통해, 요소로 올 수 있는 최대값인 2,000개 배열에 대한 소수 배열을 준비한다.

메모

잠깐, 문제에서는 요소로 올 수 있는 최대값이 1,000이라는데요?
홀수와 짝수를 더하므로, 요소의 최대값은 각 요소의 최대값을 더한 999 + 1,000 = 1,999가 됩니다.

배열이 2000개까지밖에 안 되므로, 연산할 때마다 비교하는 것 보다 미리 배열을 선언해서 비교하는 게 훨씬 효율적이라 판단했다.
만약 연산할 때마다 비교하려면, 비교할 수의 제곱근을 구하고, 2부터 제곱근까지 나눈다. 중간에 정확히 나누어 떨어지는 수가 있을 경우, 그 수는 소수가 아니다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 대상 숫자
int number = 1000;

// 소수 여부
boolean isPrime = true;

// 가장 작은 소수인 2부터 대상의 제곱근까지 나누기
for (int i = 2; i <= Math.sqrt(number); i++)
{
	// 나누어 떨어지는 수가 있을 경우
	if (number % i == 0)
	{
		isPrime = false;
		break;
	}
}

대충 위 형식처럼 짜면 된다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
for (int i = 0; i < N / 2; i++)
{
	// left[0]와 right[i]의 합이 소수일 경우
	if (!IS_NOT_PRIME[left[0] + right[i]])
	{
		selected = i;
		
		int size = bipartite();
		
		// 모든 요소가 매칭될 경우
		if (size == N / 2)
		{
			list.add(right[selected]);
		}
	}
}

그룹을 나누었으면, 입력값의 첫 번째 수 $left[0]$와 하나씩 매칭하여 기준 매칭을 선정한다. !IS_NOT_PRIME[left[0] + right[i]]을 통해 매칭이 소수일 경우에만 진행한다. 소수가 아닐 경우 비교해볼 필요도 없으니. selected는 현재 $left[0]$와 매칭된 요소를 의미한다. 이게 왜 필요하냐면, $left[0]$와 매칭된 요소의 경우 다른 요소와 매칭될 수 없으므로 매칭에서 제외해야 한다.

이는 위 그림과 같이 나타낼 수 있다. 이미 1이 10과 매칭되었으므로, 10과 연결된 7, 11의 노드를 제거해야 정상적으로 매칭할 수 있다. 연결된 노드는 hasNode 배열에서 관리하고 있다. 예제 1을 기준으로 hasNode의 값은 다음과 같다.

만약 여기서, 1과 10을 매칭할 경우 hasNode는 아래와 같다.

1과 10에 연결된 다른 노드를 모두 제거하고, hasNode[1][10] = true로 지정해야 한다. 임시 배열을 선언해서 변경하는 경우도 있겠지만, 배열 연산 오버헤드를 줄이기 위해 selected = 10으로 지정하여 DFS 알고리즘 수행 시 selected와 동일한 인덱스를 false로 인식하게끔 설계했다.

JAVA
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
/**
 * 이분 매칭 갯수 반환 함수
 *
 * @return [int] 이분 매칭 갯수
 */
private static int bipartite()
{
	// 이미 left[0]과 right 요소 하나가 선택됨
	int size = 1;
	
	matched = new int[left.length];
	
	Arrays.fill(matched, -1);
	
	for (int i = 1; i < left.length; i++)
	{
		isVisit = new boolean[left.length];
		
		// 매칭 가능할 경우
		if (dfs(i))
		{
			size++;
		}
	}
	
	return size;
}

/**
 * DFS 알고리즘 결과 반환 함수
 *
 * @param num: [int] 시작점
 *
 * @return [int] 매칭 갯수
 */
private static boolean dfs(int num)
{
	// 첫 방문일 경우
	if (!isVisit[num])
	{
		isVisit[num] = true;
		
		for (int i = 0; i < right.length; i++)
		{
			// 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
			if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
			{
				// 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
				if (matched[i] == -1 || dfs(matched[i]))
				{
					matched[i] = num;
					
					return true;
				}
			}
		}
	}
	
	return false;
}

이분 매칭 소스는 위와 같다. bipartite()는 기본적인 이분 매칭 알고리즘과 크게 다르지 않다. size가 1부터 시작하는 이유는, 이미 입력의 첫 번째 수 left[0]과 합이 소수를 만족하는 right[m]과 매칭되었기 때문이다.

dfs()에서 조건에 따라 필터링이 진행된다. 조건식은 hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]]와 같다.

• hasNode[num][i]: left[num]과 right[i]가 서로 연결되어 있는지 (소수)
• i != selected: left[num]이 right[i]와 매칭되지 않았는지
• !IS_NOT_PRIME[left[num] + right[i]]: left[num]과 right[i] 소수인지

위 조건식을 모두 만족할 경우에만 매칭을 수행한다.

$N$이 반드시 짝수거나, 입력된 숫자의 홀수, 짝수가 반드시 동일하다는 조건이 존재하지 않으므로, 이 경우 -1을 출력해야한다. 또한, 모든 조건이 일치해도 매칭이 하나도 되지 않을 경우 역시 -1을 출력해야한다.

분류

---

• 수학
• 정수론
• 소수 판정
• 이분 매칭
• 에라토스 테네스의 체