글 읽기 - 2초 남기고 97%에서 틀립니다.. 뭐가 문제일까요...

zzangnyun 5년 전 0

질문 검색에 많이 올라온 홀수, 짝수 나누는 정답 코드와는 조금 다른 방법으로 짜보았습니다.

이분 매칭을 공부하고 예제 겸해 풀어보았는데 계속 97%에서 틀리네요.

주석 최대한 달아놓았습니다...ㅠㅠ!!

답변 미리 감사드립니다......

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <functional>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef pair<int, int> pii;
#pragma warning(disable:4996)

const int MAX_N = 55;
int N;
int arr[MAX_N];
int aMatch[MAX_N], bMatch[MAX_N];
vector<int> adj[MAX_N];
bool visited[MAX_N];

// 소수인지 판별 그냥 2부터 a-1까지 다 나누어 봅니다.
bool isPrime(int a) {
	for (int i = 2; i < a; i++) {
		if (a % i == 0) return false;
	}
	return true;
}

// 이분 매칭 dfs
bool dfs(int a) {
	if (visited[a]==true)
		return false;
	visited[a] = true;
	for (int i = 0; i < adj[a].size(); i++) {
		int b = adj[a][i];
		if (bMatch[b] == -1 || dfs(bMatch[b])) {
			aMatch[a] = b;
			bMatch[b] = a;
			return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
	}

	// p는 첫번째 수와 더해져 소수를 이루는 수의 인덱스를 저장합니다.
	vector<int> p;
	int index_one = arr[1];
	
	for (int i = 2; i <= N; i++) {
		if (isPrime(arr[i] + index_one))
			p.push_back(i);
	}

	// 만약 첫번째 수와 더해져 소수를 만드는 수가 없으면 바로 종료합니다.
	if (p.size() == 0) {
		printf("-1");
		return 0;
	}

	vector<int> res;
	for (int t = 0; t < p.size(); t++) {
		// 벡터 p에 담긴 인덱스들은 제외하고 나머지 수들에 대해 이분매칭 그래프를 만듭니다.
		// notin은 이분매칭에서 제외되는 수의 인덱스 번호입니다.
		int notin = p[t];

		for (int i = 2; i <= N; i++) {
			for (int j = 2; j <= N; j++) {
				// i, j가 notin일 때, 그리고 같을 때는 그냥 넘어갑니다.
				if (i == j || i == notin || j == notin)
					continue;

				// 만약 두 수의 합이 소수를 이루면 두 수를 연결해줍니다.
				int k = arr[i] + arr[j];
				if (isPrime(k)) {
					adj[i].push_back(j);
				}
			}
		}

		// 이분 매칭 //
		fill(aMatch, aMatch + N + 5, -1);
		fill(bMatch, bMatch + N + 5, -1);
		
		int ret = 0;
		for (int i = 2; i <= N; i++) {
			if (i != notin) {
				if (aMatch[i] == -1) {
					fill(visited, visited + N + 5, false);
					if (dfs(i))
						ret++;
				}
			}
		}
		// 이분 매칭 //
		
		// 첫번째 수와, 그와 소수를 이루는 제외하고 이분매칭을 했을 때
		// 모두가 매칭이 되어야 하므로 ret가 N-2일 때 notin 인덱스의 수를 res에 저장합니다.
		if (ret == N - 2) {
			res.push_back(arr[notin]);
		}
	}

	// res에 아무것도 들어오지 않으면 -1
	if (res.size() == 0) {
		printf("-1");
	}
	// 그외의 경우 정렬하고 출력
	else {
		sort(res.begin(), res.end());
		for (int i = 0; i < res.size(); i++) {
			printf("%d ", res[i]);
		}
	}
	
}