[백준 3671] 산업 스파이의 편지 (C++)

문제

---

안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요.

저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다.

저를 고용한 사람은 매우 무서운 사람입니다. 또, 저는 프로이기 때문에 실수를 용납하지 않습니다. 어떻게든 이 종이를 모두 복구해가야합니다. 이 연구소의 연구 주제는 빠른 소인수 분해입니다. 제가 가진 종이 조각에는 숫자가 한 자리씩만 적혀져 있습니다. 원래 숫자가 뭐였는지를 잘 모르겠습니다. 종이 조각에 쓰여 있는 숫자를 보내드릴테니, 종이 조각을 적절히 배치해서 소수가 되는 경우가 몇 개이지 알려주실 수 있나요?

감사합니다.

스파이 드림.

 

입력

---

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200) 각 테스트 케이스는 한 줄로 이루어져 있고, 종이조각에 쓰여 있는 수가 공백없이 주어진다. 종이조각의 수는 적어도 1개, 많아야 7개이다.

 

출력

---

각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, 17, 71이다) 종이 조각을 적절히 배치해서 만든 숫자가 0으로 시작할 때, 앞에있는 0을 지운 수가 같으면 같은 숫자이다.

 

문제 풀이

---

브루트포스 문제.

 

에라토스테네스의 체로 소수 판정을 한 후, 종이조각으로 만들어질 수 있는 모든 가능한 수에 대해 해당 수가 소수라면 set에 넣어 그 개수를 출력하면 된다.

종이조각으로 만들 수 있는 가능한 수를 구하는 방법은 N과 M 시리즈 문제를 참조하면 된다. 해당 문제에서 최대 depth가 N까지 였다면 여기에서는 1부터 문자열의 길이까지 모든 가능한 경우의 수를 찾아주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

int* makeArr;
int* arr;
int N;
bool* isVisited;
bool* isPrime;
set<int> answers;

void find(int depth, int maxDepth)
{
	if (depth == maxDepth)
	{
		int num = 0;
		for (int i = 0; i < maxDepth; i++)
		{
			num = num * 10 + makeArr[i];
		}
		if (isPrime[num] == true)
		{
			answers.insert(num);
		}
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			if (isVisited[i] == false)
			{
				isVisited[i] = true;
				makeArr[depth] = arr[i];
				find(depth + 1, maxDepth);
				isVisited[i] = false;
			}
		}
	}
}

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

	isPrime = new bool[10000001];
	for (int i = 0; i < 10000001; i++)
	{
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i <= sqrt(10000000); i++)
	{
		for (int j = 2 * i; j <= 10000000; j += i)
		{
			isPrime[j] = false;
		}
	}
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		answers.clear();
		string str;
		cin >> str;
		N = str.length();
		arr = new int[N];
		makeArr = new int[N];
		isVisited = new bool[N];
		for (int i = 0; i < N; i++)
		{
			isVisited[i] = false;
			arr[i] = str.at(i) - 48;
		}
		for (int i = 1; i <= N; i++)
		{
			find(0, i);
		}
		cout << answers.size() << "\n";
	}
	return 0;
}