글 읽기 - 시간초과 질문

jng6017 4년 전 0

int t, s; // t : 첫 번째 수로 기준 정하기, s : 홀, 짝 크기

vector l[2], ans; // l[0] : 짝수, l[1] : 홀수, ans는 정답

bool p[2001], v[51], D; // p : 소수, v : 방문 여부, D : 최종 목적지 도달 여부

처음 받은 수를 n%2를 통해 판별하여 t에 기준을 넣어주었습니다. 짝수면 0, 홀수면 1

그리고 반대 편을 1-t를 통해 잡아주어 v[i]를 통해 방문 해주었습니다.

8퍼에서 시간초과가 뜨네여....

이분 매칭 이용해서 푼거 같은데 시간초과가 뜨길래 무슨 이유인지 궁금해서 여쭤보게되었습니다.

혹시 제가 푼 방식이 이분 매칭이 아니거나, 잘못 접근을 한 것 인가요??

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

int t, s;                  // t : 첫 번째 수로 기준 정하기, s : 홀, 짝 크기
vector<int> l[2], ans;     // l[0] : 짝수, l[1] : 홀수, ans는 정답
bool p[2001], v[51], D;    // p : 소수, v : 방문 여부, D : 최종 목적지 도달 여부

void setPrime() {
	int i, j;
	p[1] = true;
	for (i = 2; i*i <= 2000; i++) {
		if (!p[i]) {
			for (j = i + i; j <= 2000; j += i)
				p[j] = true;
		}
	}
}

void checkPair(int inx) {
	int i;
	if (inx == s)
		D = false;
	else {
		for (i = 0; D && i < s ; i++) {
			if (!v[i]) {
				if (!p[l[t][inx] + l[1 - t][i]]) {
					v[i] = true;
					checkPair(inx + 1);
					v[i] = false;
				}
			}
		}
	}
}

int main() {
	int N, i;
	cin >> N;
	for (i = 0; i < N; i++) {
		int n;
		cin >> n;
		if (i == 0)
			t = n % 2;
		l[n % 2].push_back(n);
	}
	if (l[t].size() == l[1 - t].size()) {
		setPrime();
		s = l[t].size();
		for (i = 0, D = true; i < s; i++, D = true){
			if (!p[l[t][0] + l[1 - t][i]]) {
				v[i] = true;
				checkPair(1);
				v[i] = false;
				if (!D)
					ans.push_back(l[1 - t][i]);
			}
		}
	}
	if (ans.size()) {
		sort(ans.begin(), ans.end());
		for (i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
	}
	else
		cout << -1;
	return 0;
}

djm03178 4년 전 0

네, 이분 매칭이 아닙니다. 정확히는 '이분 매칭 알고리즘'을 쓰지 않았습니다.

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

문제

문제

출처

ICPC

시간초과 질문

jng6017 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말