[BOJ] 3671 - 산업 스파이의 편지

1. 문제 해석

https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

• 최소 1개, 최대 7개의 숫자가 주어진다.
• 숫자를 적절하게 배치하여 만들 수 있는 소수의 개수를 구해야 한다.
• 주어진 수 중에 일부만 사용해도 된다. 만들어진 수가 0으로 시작할 경우 0을 지운다.

 

2. 접근방법

최대 7개의 수가 주어지기 때문에 만들 수 있는 조합의 개수는 7!이다. 조합으로 만들어진 수가 소수인지 판단하여 카운팅 해주면 될 것이다.

• 에라토스테네스의 체를 이용하여 7자리까지 만들 수 있는 소수를 배열 chk에 모두 체크해 둔다.
• 재귀함수를 이용하여 주어진 수를 조합한 수 num을 만든다.
• 만들어진 수 num이 chk[num] == true를 만족한다면 소수 개수를 카운팅 한다.

 

3. 주의할 점

• 여러 개의 테스트 케이스가 주어지기 때문에 초기화해야 할 것들을 생각해야 한다.
• 11과 011은 같은 수이다. 

 

4. 소스코드

#include <iostream>
#include <string>
#include <set>

using namespace std;

int a[10];
int aSize;
int ans;
set<int> numSet;
bool vis[10];
bool chk[10000000];

void init(string str) {
	aSize = str.size();
	for (int i = 0; i < str.size(); i++) {
		a[i] = str[i] - '0';
	}
	for (int i = 0; i < 10; i++) vis[i] = false;
}

void sol(int num) {
	if (num > 1) {
		if (!chk[num]) {
			if (numSet.find(num) == numSet.end()) {
				numSet.insert(num);
				ans++;
			}
		}
	}

	for (int i = 0; i < aSize; i++) {
		if (!vis[i]) {
			vis[i] = true;
			sol(num * 10 + a[i]);
			vis[i] = false;
		}
	}
}

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

	// 소수
	for (int k = 2; k * k < 10000000; k++) {
		if (chk[k]) continue;
		for (int i = k * k; i < 10000000; i += k) {
			chk[i] = true;
		}
	}

	int T;
	cin >> T;
	while (T--) {
		string str;
		cin >> str;
		init(str);
		numSet.clear();
		ans = 0;
		sol(0);
		cout << ans << '\n';
	}

	return 0;
}