[1017] 소수 쌍

https://www.acmicpc.net/problem/1017

처음엔 이분 매칭 문제인 것을 모르고..

엄청나게 틀렸네요... 시간초과 + 구현실수....

알고나서도 한참을 해맸는데요!

첫번째 이유는 첫번째 수와 매칭되는 수를 출력한다는 점이었어요..

소수 쌍을 구하는 것이기 때문에

홀수 + 홀수 = 짝수(2를 제외하고는 무조건 소수가 안됨)

짝수 + 짝수 = 짝수(무조건 안됨)

홀수 + 짝수 = 홀수(가능성 있음)

입니다!

그렇기 때문에 그룹을 홀수와 짝수로 나누어야하는데요!

첫번쨰 수가 홀수일수 도있고 짝수일 수도 있기 때문에 어떻게 진행해야할지 난해했습니다.

두번째 소수를 구하는 방법입니다. 풀고나니깐 뭐.. 에라토스테네스의 체를 써도 되고 그냥 나눠서 확인해도

입력받는 수가 1000까지기 때문에 최대 1999(두 수를 합쳐야하므로)밖에 안되서 오래걸리진 않습니다.

마지막으로 출력입니다. 입력이 정렬되서 들어온다는 말은 없으므로 출력할 때 정렬을 해야합니다.

저같은 경우는 우선순위 큐에 넣어서 그냥 큐가 빌때까지 출력했습니다.

-1이 출력되는 조건은 큐가 비어있다면 -1을 출력했습니다.

문제 해결 전략은

1. 첫번째 수와 다른 그룹의 수와 매칭을 시킨다.

2. 1에서 매칭된 수가 소수라면 1에서 매칭된 쌍을 제외하고 이분매칭 알고리즘을 이용해서 나머지를 매칭합니다.

3. 만약 전부 매칭해서 매칭 된 수가 입력 받은 N의 절반이 된다면 전부 매칭된 것이므로 우선순위 큐에다가 처음에 첫번째 수와 매칭한 수를 푸시해줍니다.

4. 위의 과정을 다른 그룹의 수의 개수만큼 반복합니다.

아래는 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 50
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int arrA[MAX_SIZE];
int arrB[MAX_SIZE];
int pick;
int idxA, idxB;
 
int matchA[MAX_SIZE];
int matchB[MAX_SIZE];
bool visit[MAX_SIZE];
 
bool isPrime(int a) {
    if (a == 1) return 0;
    else if (a != 2 && a % 2 == 0) return 0;
    
    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return 0;
    }
 
    return 1;
}
 
bool f(int idx) {
    if (visit[idx]) return 0;
    visit[idx] = 1;
 
    for (int i = 0; i < idxB; i++) {
        if (i == pick) continue;
 
        if (isPrime(arrA[idx] + arrB[i]) && (matchB[i] == -1 || !visit[matchB[i]] && f(matchB[i]))) {
            matchB[i] = idx;
            matchA[idx] = i;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    int arr[MAX_SIZE];
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    for (int i = 0; i < n; i++) {
        if (arr[0] % 2 == arr[i] % 2) arrA[idxA++] = arr[i];
        else arrB[idxB++] = arr[i];
    }
 
    priority_queue<int> pq;
 
    for (int i = 0; i < idxB; i++) {
        if (isPrime(arrA[0] + arrB[i])) {
            pick = i;
            
            int cnt = 1;
            memset(matchA, -1, sizeof(matchA));
            memset(matchB, -1, sizeof(matchB));
 
            for (int j = 1; j < idxA; j++) {
                memset(visit, 0, sizeof(visit));
                if (f(j)) cnt++;
            }
 
            if (cnt == n / 2) pq.push(-arrB[i]);
        }
    }
 
    if (pq.empty()) puts("-1");
    else {
        while (!pq.empty()) {
            printf("%d ", -pq.top()), pq.pop();
        }
    }
 
    return 0;
}