#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

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 위의 경우 정답은 4, 10이다.

입력:

첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

풀이:

너무 여러워서 답을 봐도 이해가 안되기 때문에 나중에 다시 풀어봐야겠다.

코드:

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[25];
int matchA[25] = {-1, }, matchB[25] = {-1,};
bool visited[25] = {false,};

bool dfs(int a){
	if(visited[a]) return false;
	visited[a] = true;
	for(int b: adj[a]){
		if(matchB[b] == -1||dfs(matchB[a])){
			matchA[a]=b;
			matchB[b]=a;
			return true;
		}
	}
	return false;
}

int main(void){
	int n;
	cin >> n;
	vector<int> A, B;
	bool first_value_odd = false;
	for(int i = 0; i<n; i++){
		int number;
		cin >> number;
		//divide even or odd
		if(i==0 && number % 2) first_value_odd = true;
		(number%2 ? A, B).push_back(number);
	}
	
	if(A.size() != B.size()){
		cout<<-1;
		return 0;
	}
	
	if(!first_value_odd) swap(odd, even);
	
	//sieve of eratosthenes
	bool isPrime[1000] = {true,}
	for(int i = 3; i<2000; i++){
		if(!isPrime([i/2]) continue;
		for(int j = i*i; j<2000; j+=i*2){
			isPrime[j/2] = false;
		}
	}
	
	vector<int> result;
	//bipartite matching
	for(int i: adj[0]){
		int flow = 1;
		matchA[0] = i;
		matchB[i] = 0;
		for(int j=1; j<listSize; j++){
			visited[0] = true;
			if(dfs(j)) flow++;
		}
	}
	if(result.empty()) puts("-1");
    else{
        sort(result.begin(), result.end());
        for(int r: result)
            printf("%d ", r);
    }
}