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

문제 링크: https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

1. 주의할 점

- 소수인 수를 미리 구해놓는다

- 매 TC마다 벡터들을 초기화한다

 

2. 구현

- 에라토스테네스의 체를 이용하여 소수면 Num[] 배열 자기자신을 입력한다

- 1~입력받은 수의 자리수 까지 DFS를 수행하며 구한 수가 소수라면 Set에 넣는다

 

#define MAX 10000000
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdlib.h>
#include <set>
#include <math.h>
using namespace std;
int num[MAX], len;
bool check[7];
vector<int> v, ans;
set<int> s;
string str;

void cal() {
	for (int i = 2; i < MAX; i++) 
		num[i] = i;
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (num[i] == 0) continue;
		for (int j = i + i; j < MAX; j += i)
			num[j] = 0;
	}
}

void dfs(int idx, int len) {
	if (idx==len) {
		string ss = "";
		for (int i = 0; i < idx; i++)
			ss += (ans[i]+'0');
		int val = stoi(ss);
		if (num[val] != 0)
			s.insert(val);
		return;
	}

	for (int i = 0; i < str.size(); i++) {
		if (check[i]) continue;
		ans.push_back(v[i]);
		check[i] = true;
		dfs(idx + 1, len);
		ans.pop_back();
		check[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cal();
	int test;
	cin >> test;
	for (int t = 0; t < test; t++) {
		v.clear();
		s.clear();
		cin >> str;
		len = str.size();
		for (int j = 0; j < len; j++) {
			check[j] = false;
			int val = str[j] - '0';
			v.push_back(val);
		}
		for (int j = 1; j <= len; j++) {
			ans.clear();
			dfs(0, j);
		}
		cout << s.size() << '\n';
	}
	return 0;
}