[UVa][C++] 524: Prime Ring Problem (소수 고리 문제)

문제 링크: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=465

 

고리 안에 있는 인접한 두 개의 숫자의 합이 소수인 고리를 찾는 것이 문제입니다. 고리의 시작은 1로 고정돼있습니다.

입력의 범위가 \(0<n\leq16\) 인 점을 생각하시면, 합이 31 이하 소수들이 될 것이라는 점을 예상할 수 있습니다.

31 이하 소수는 \([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]\) 이렇게 11개가 있습니다.

 

dfs로 풀면 됩니다.

출력 형식에 유의하세요.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

int n;
bool primes[32];
bool visited[17];
vector<vector<int>> answer;

void dfs(vector<int>& circle, int current) {
	if (current == n) {
		for (auto it = circle.begin(); it != circle.end(); ++it) {
			cout << *it;
			if (it + 1 != circle.end()) cout << ' ';
		}
		cout << '\n';
		return;
	}



	int sum;
	for (int candidate = 2; candidate <= n; ++candidate) {
		sum = circle[current-1] + candidate;
		if (!visited[candidate] && primes[sum]) {
			//끝부분인 경우
			if (current == n-1 && !primes[circle[0] + candidate]) {
				continue;
			}

			circle[current] = candidate;
			visited[candidate] = true;

			dfs(circle, current + 1);

			visited[candidate] = false;
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	primes[2] = primes[3] = primes[5]
		= primes[7] = primes[11] = primes[13]
		= primes[17] = primes[19] = primes[23]
		= primes[29] = primes[31] = true;

	int cnt = 0;
	while (cin >> n) {
		if (cnt != 0) cout << "\n";
		cout << "Case " << ++cnt << ":\n";

		answer.clear();

		vector<int> circle;
		circle.resize(n);
	
		circle[0] = 1;
		visited[0] = true;
		dfs(circle, 1);
	}
	
	return 0;
}