[BOJ | 백준] 3671번: 산업 스파이의 편지

by Kimcoding on 2020-03-31 04:39

in BOJ

문제 설명

BOJ 3671

주어진 수열로 숫자를 만들었을 때 그 수가 소수인지 판별하는 문제입니다.

풀이

우선 소수 판별을 짧은 시간안에 구해야하니 에라토스테네스의 체로 1000만까지 소수 판별을 미리 구하겠습니다. O(NlglgN)

루트 N까지 검사하여 시간을 더 줄여줍니다.

그 다음에 주어진 수열로 모든 경우의 수를 봅니다. O(7!)

중복을 map으로 판별하고 중복이 아니라면 소수인지 판별하고 정답에 더해줍니다.

에라토스테네스의 체로 소수를 빨리 구할 수 있다면 어렵지 않은 문제였습니다.

원래 next_permutation 함수를 별로 좋아하지는 않지만 귀찮아서 썼습니다 하하…

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX 10000000
using namespace std;

int main() {
	FIO;
	bool prime[MAX];
	memset(prime, 1, sizeof(prime));
	prime[0] = prime[1] = 0;
	for (int i = 2; i * 2 < MAX; i++)
		prime[i * 2] = 0;
	for (int i = 3; i * i < MAX; i += 2) {
		if (!prime[i]) continue;
		for (int j = i * 2; j < MAX; j += i) prime[j] = 0;
	}

	int t; cin >> t; while (t--) {
		string s; cin >> s;
		bool visit[10] = {};
		int arr[10], len = s.size(), ans = 0;
		for (int i = 0; i < len; i++)
			arr[i] = s[i] - '0';
		map <int, int> m;
		sort(arr, arr + len);
		do {
			int x = 0;
			for (int i = 0; i < len; i++) {
				x = 10 * x + arr[i];
				if (m.find(x) != m.end()) continue;
				m[x] = 1;
				if (prime[x]) ans++;
			}
		} while (next_permutation(arr, arr + len));
		cout << ans << '\n';
	}
	return 0;
}