ACMICPC 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을 출력한다.

이분 매칭을 응용해서 푸는 문제이다. (이분 매칭에 관해서는 이곳에서 공부할 수 있다)

양 그래프의 정점은 입력받은 숫자들로 채워넣고, 엣지는 두 정점의 합이 소수일 경우에만 이어지도록 코딩해준다.

이를 위해서 getPrime() 함수와 add2node()함수를 사용했다 - 코드 참조 -

이렇게 이분 그래프를 완성시키고 나면 약간의 예외를 포함한 단순한 이분 매칭 문제로 바뀌게 된다.

일단 첫 노드의 연결이 중요하기 때문에 첫 노드만 임의로 연결을 시켜주고, 나머지 노드들에 대한 이분 매칭을

실행해주면 된다.

이분 매칭이 종료되었을 때 연결된 엣지의 수가 n 과 같으면 모두 연결된 것이니 answer Vector에 채워 넣으면 된다.

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; int n, list[51]; bool prime[2001]; vector<int> node[51]; vector<int> answer; int matching[51], matched, m; bool isVisited[51]; void getPrime(); bool add2node(int cur, int num); bool dfs(int cur); int main() { memset(prime, true, sizeof(prime)); getPrime(); scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &list[i]); for (int i = 0; i < n; i++) { node[i].reserve(50); for (int j = 0; j < n; j++) { if (add2node(list[i], list[j])) node[i].push_back(j); } } for (int i = 0; i < node[0].size(); i++) { memset(matching, -1, sizeof(matching)); m = node[0][i]; matched = 2; // printf("\n\n%d - %d\n", list[0], list[m]); matching[m] = 0; matching[0] = m; for (int i = 1; i < n; i++) { memset(isVisited, false, sizeof(isVisited)); if (i != m && dfs(i)) matched++; } if (matched == n) answer.push_back(list[m]); } if (answer.empty()) printf("-1\n"); else { sort(answer.begin(), answer.end()); for (int i = 0; i < answer.size(); i++) printf("%d ", answer[i]); printf("\n"); } } void getPrime() { for (int i = 2; i <= 2000; i++) { if (prime[i] == false) continue; for (int j = i * 2; j <= 2000; j += i) prime[j] = false; } } bool add2node(int cur, int num) { if (cur == num) return false; if (prime[cur + num]) return true; return false; } bool dfs(int cur) { if (isVisited[cur]) return false; isVisited[cur] = true; for (int i = 0; i < node[cur].size(); i++) { int next = node[cur][i]; if (matching[next] == 0 || next == 0 || !prime[list[cur] + list[next]]) continue; if (matching[next] == -1 || dfs(matching[next])) { matching[next] = cur; // printf("%d - %d\n", list[cur], list[next]); return true; } } return false; }