글 읽기 - 하 어디가 문제인지 모르겠습니다 ㅠㅠ!

wnsgurl97 2년 전 0

반례가 무엇일까요 ㅠㅠㅠㅠ

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define FOR2(i, n) for(int i = 0; i < n; ++i)
#define FOR3(i, n, m) for(int i = n; i < m ; ++i)
using namespace std;

bool isPrime[1005];
int arr[55], N;
vector<int> ans;
vector<int> prime;

void swap(int *n, int* m) {
	int t = *n;
	*n = *m;
	*m = t;
}

bool DFS(int start) {

	if (start == N)
		return true;

	FOR3(i, start + 1, N) {
		if (isPrime[arr[i] + arr[start]]) {
			swap(&arr[start + 1], &arr[i]);
			if (DFS(start + 2)) {
				if (start == 0) {
					ans.push_back(arr[1]);
					swap(&arr[start + 1], &arr[i]);
				}
				else {
					swap(&arr[start + 1], &arr[i]);
					return true;
				}
			}
			else
				swap(&arr[start + 1], &arr[i]);
		}
	}

	return false;
}

void findPrime(int p) {
	FOR3(i, 2, 501) {
		if (p * i > 1002)
			return;
		isPrime[p * i] = false;
	}
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(isPrime, true, 1005);
	FOR3(i, 2, 1001){
		if(isPrime[i])
			findPrime(i);
	}

	cin >> N;
	FOR2(i, N) {
		cin >> arr[i];
	}

	DFS(0);

	if (ans.empty())
		cout << -1 << '\n';
	else {
		sort(ans.begin(), ans.end());
		FOR2(i, ans.size()) {
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

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

문제

문제

출처

ICPC

하 어디가 문제인지 모르겠습니다 ㅠㅠ!

wnsgurl97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말