처음 이 문제를 접했을 때에는 '혹시 쌍둥이 소수' 문제일까 하고 봤었네요. 소수쌍이 아니라 합이 소수가 되는 숫자들의 합 이야기입니다. 짝수인 N개가 주어지면, 합이 소수가 되는 쌍으로 모두 묶을 수 있다면, 첫번째 수와 묶일 수 있는 수들의 리스트를 내는 문제입니다. 난이도는 Platinum III이지만, 난이도보다는 쉬운 문제입니다. 물론 네트워크 플로우 알고리즘을 알고 있을 때에 한합니다. DFS 알고리즘으로도 풀 수 있지만, 그렇게 하면 시간초과가 납니다.
아래는 해당 문제의 링크입니다.
https://www.acmicpc.net/problem/1017
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 수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는
www.acmicpc.net
이 문제에서는 소수를 빨리 찾는 방법이 관건입니다. 리스트에 있는 수들의 50개이므로, 첫번째수와 연결되는 두번째 수를 선택하고 나머지에 대해서 소수쌍이 되는지 검사하면 됩니다. 미리 매칭 테이블을 만들어놓아서 한다면, 최대 \(25 \times 49=1225\)번의 소수 검사만 하면 됩니다. 나올 수 있는 소수 크기가 2,000 미만이므로 소수 검사비용도 상당히 저렴합니다.
알고리즘은 간단합니다.
첫번째 수는 당연히 필요한 것이고, 두번째 수를 차례대로 선택한 후, 이 합이 소수이면, 나머지 수들에 대해서는 네트워크플로우를 이용해서 소수쌍으로 모든 수들이 참여가능한지 판단합니다. 그렇게 판단이 되면 두번째 수를 출력하고 이 과정을 반복하면 됩니다.
'Programming > BOJ' 카테고리의 다른 글
| 백준 #1019 책 페이지 (0) | 2019.12.25 |
|---|---|
| 백준 #1018 체스판 다시 칠하기 (0) | 2019.12.24 |
| 백준 #1016 제곱 ㄴㄴ수 (0) | 2019.12.24 |
| 백준 #1015 수열 정렬 (0) | 2019.12.23 |
| 백준 #1012 유기농 배추 (0) | 2019.12.22 |
댓글