글 읽기 - 틀린 이유를 잘 모르겠습니다..

psjinqkr 5년 전 0

어디가 틀린걸까요ㅜㅜ

부탁드립니당

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;

int n;
int *visited;
int *input;
vector<int> first;
bool couple(int a, int b);
bool check(int num);
int main() {
	cin >> n;
	visited = (int*)malloc(sizeof(int)*n);
	input = (int*)malloc(sizeof(int)*n);

	for (int i = 0; i < n; i++) {
		visited[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}

	for (int i = 1; i < n; i++) {
		if (couple(0, i)) {
			first.push_back(input[i]);
			
			for (int j = 0; j < n; j++) {
				visited[j] = 0;
			}
		}
	}

	if (first.size() != 0) {
		sort(first.begin(), first.end());
		for (int i = 0; i < first.size(); i++) {
			cout << first[i] << " ";
		}
	}
	else
		cout << -1;
	//system("pause");
}

bool couple(int a, int b) {
	//a+b가 소수일때
	//a+b가 소수가 아닐때

	if (!check(input[a] + input[b]))
		return false;
	else {
		//cout << input[a] << "와" << input[b]<<endl;
		visited[a] = 1;
		visited[b] = 1;
		for (int i = 1; i < n; i++) {
			if (visited[i] == 0) {
				for (int j = i + 1; j < n; j++) {
					if (visited[j] == 0)
						if (!couple(i, j))
							return false;
				}
			}

		}
	}

	return true;
}

bool check(int num) {
	int result = 0;
	for (int i = 1; i <= num; i++) {
		if (num%i == 0)
			result++;
	}
	if (result == 2)
		return true;
	else
		return false;
}

rhs0266 5년 전 0

WA를 받으신 이유는 아마도 visit 초기화를 couple이 통과됐을 때만 수행했기 때문일 것 같습니다. 하지만 고치셔도 TLE를 받을 것 같습니다. 왜냐하면 현재 풀이는 최악의 경우 25!보다 오래 걸릴 것 같기 때문인데요, brute force보다 좋은 방법이 있으니 찾아보시는 게 좋을 것 같습니다.

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

문제

문제

출처

ICPC

틀린 이유를 잘 모르겠습니다..

psjinqkr 5년 전 0

rhs0266 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말