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

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

3671번: 산업 스파이의 편지

비주얼 스튜디오에서는 sqrt() 함수가 잘 동작해서 그대로 제출했는데 컴파일 에러가 났다.

비주얼 스튜디오에서는 에러가 없어도 <cmath>를 꼭 포함하는거 잊지 말자

그리고 소수 구할 때 n / 2까지 나눠보지 않아도 루트 n까지만 나눠봐도 된다. 이걸 몰라서 계속 시간초과가 났다.

절대 잊지 말자.

소수인지 아닌지 판별할 때에는 n / 2까지 굳이 나눠보지 않아도 루트 n까지 나눠보면 된다

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

set<int> st;

void combination(vector<bool> visited, vector<int> result, int n, int k, int num, int* arr) {
	if (num == k) {
	
		do {
			string str = "";
			for (int i = 0; i < k; i++) {
				str += (result[i] + '0');
			}
			int number = stoi(str);
			bool flag = true;
			if (number % 2 == 1) {
				for (int i = 2; i <= sqrt(number); i++) {
					if (number % i == 0) {
						flag = false;
						break;
					}
				}
			}
			else {
				flag = false;
			}
			if (number == 1 || number == 0) flag = false;
			if (number == 2) flag = true;
			if (flag) {
				st.insert(number);
			}

		} while (next_permutation(result.begin(), result.end()));
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num == 0) {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = arr[i];
				combination(visited, result, n, k, num + 1, arr);
				visited[i] = false;
			}
		}
		else {
			if (!visited[i] && result[num - 1] <= arr[i]) {
				visited[i] = true;
				result[num] = arr[i];
				combination(visited, result, n, k, num + 1, arr);
				visited[i] = false;
			}
		}
	}
}

int main() {
	int c;
	cin >> c;
	for (int t = 0; t < c; t++) {
		st.clear();
		string s;
		cin >> s;
		int* arr = new int[7];
		for (int i = 0; i < s.size(); i++) {
			arr[i] = s[i] - '0';
		}
		sort(arr, arr + s.size());
		for (int i = 1; i <= s.size(); i++) {
			vector<bool> visited(s.size());
			vector<int> result(i);
			combination(visited, result, s.size(), i, 0, arr);
		}
		cout << st.size() << '\n';
	}
	return 0;
}