글 읽기 - [C++] 반례를 못찾겠습니다.. 고수님들 도와주세요

sure97 4년 전 0

에라스토테네스의 체를 이용해 2000까지의 수가 소수인지 판별하였고( i 가 소수일시 prime[i] = false)

입력받은 수들이 홀수인지 짝수인지 구분해서 odd배열에 저장했습니다

그 뒤 각 수들을 더한 값이 홀수이면 edge를 연결해주었습니다

첫번째 수와 연결된 수를 고정시킨 채로 다른 수들 중 홀수/짝수 여부가 첫번째 수와 같은 수로만 이분매칭 해주어서 연결이 될 경우 ans벡터에 넣어주고 ( 이 때 dfs함수에서 첫번째 수와 연결된 값은 바뀌지 못하게 설정했습니다. ) ans벡터를 정렬해서 출력했습니다

문제 조건에 모두 맞게 푼 것 같은데 틀렸습니다가 나오네요 ㅠ 반례가 있을까요?

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n, x;
bool prime[2002], visit[52];
vector<int> v[52], ans;
int num[52], whoget[52], odd[52];

bool dfs(int i) { //이분매칭 dfs
	if (visit[i] || i == 1) return false;
	visit[i] = true;
	
	for (auto k : v[i]) {
		if (!whoget[k] || dfs(whoget[k])) {
			whoget[k] = i;
			return true;
		}
	}
	return false;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
		odd[i] = num[i] % 2;
	}
	for (int i = 2; i * i <= 2000; i++) {//에라스토테네스의 체
		if (!prime[i]) {
			for (int j = i * 2; j <= 2000; j += i) {
				prime[j] = true;
			}
		}
	}


	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (!prime[num[i] + num[j]]) {
				v[i].push_back({ j });
				v[j].push_back({ i });
			}
		}
	}
	int cmp = odd[1]; //1번째 수가 홀수인지 짝수인지
	for (auto k : v[1]) {
		bool flag = false;
		memset(whoget, 0, sizeof(whoget));
		whoget[k] = 1;
		for (int i = 2; i <= n; i++) {
			if (odd[i] != cmp) continue;
			memset(visit, false, sizeof(visit));
			if (!dfs(i)) {//리턴값이 false면 매칭이 되지 않음
				flag = true;
				break;
			}
		}
		
		if (flag) continue;
		ans.push_back({ num[k] });
	}
	sort(ans.begin(), ans.end());
	if (ans.empty())
		cout << "-1\n";
	else {
		for (auto u : ans)
			cout << u << " ";
		cout << "\n";
	}
}

sure97 4년 전 4

해결했습니다 !

입력 중 홀수 개수와 짝수 개수가 다를 경우, -1을 출력해야하는데 한 쪽으로만 매칭을 시도해서 오답을 출력하는 사례가 있었네요 ㅠ

ex)

8
1 4 7 10 11 12 14 16

정답 : -1 / 출력 : 4 10 16

홀수 개수와 짝수 개수가 다른 경우 -1을 출력하는 조건을 추가해주니 맞았습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 반례를 못찾겠습니다.. 고수님들 도와주세요

sure97 4년 전 0

sure97 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말