[C++/3671] 산업 스파이의 편지

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

DFS와 구현으로 문제를 해결했습니다. 주어진 최대 7자리의 숫자를 전부 1의 자리로 나눠서 모두 숫자로 만들어서 vector에 삽입해둔 다음에, 주어진 값을 모든 경우의 수를 생성해 소수인지 판단하는 문제입니다. 구현할 때 여러 TestCase가 존재하기 때문에 초기화를 잘 쳐야하고, 중복된 값이 계속해서 답이 될 수 있기 때문에 map을 사용해서 이미 정답으로 체점했던 소수들은 제외하고 정답을 체크했습니다. 아래는 정답코드입니다.

문제를 좀 더럽게 풀었습니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>

#define MAX 10000000
using namespace std;

int testCase,answer;
string number;

map<int,int> m;
vector<int> divideNum;
vector<bool> checkPrime;

void checkPrimeNumber() {
	
	int n = 9999999;
	checkPrime.assign(n + 1, true);
	
	for(int i = 2; i * i <= n; i++){
		if(checkPrime[i]){
			for(int k = i * i; k <= n; k += i){
				checkPrime[k] = false;
			}
		}
	}
	
	checkPrime[1] = false;
	checkPrime[0] = false;
	
}

int visited[11];

void divideNumber(string num) {
	divideNum.clear();
	for(int i = 0; i < num.length(); i++){
		divideNum.push_back(num[i] - '0');
	}
	
}

vector<int> v;

void dfs(int cnt, int current) {
	
	if(cnt == current) {
		
		int primeNumber = 0;
         
        for(int i = 0; i < v.size(); i++){
            primeNumber += v[i];
            primeNumber *= 10;
        }
        
		if(primeNumber) primeNumber /= 10;
		
		if(checkPrime[primeNumber] && !m[primeNumber]){
			m[primeNumber] = 1;
			answer++;
		}
		
		return;
		
	}
	
	for(int i = 0; i < divideNum.size(); i++){
		if(!visited[i]){
			visited[i] = 1;
			v.push_back(divideNum[i]);
			dfs(cnt, current + 1);
			visited[i] = 0;
			v.pop_back();
		}
	}
	
}

int solve() {
	
	memset(visited,0,sizeof(visited));
	answer = 0;
	for(int i = 1; i <= divideNum.size(); i++){
		for(int j = 0; j < divideNum.size(); j++){
			if(!visited[j]){
				visited[j] = 1;
				v.push_back(divideNum[j]);
				dfs(i,1);
				v.pop_back();
				visited[j] = 0;	
			}
		}
	}
	return answer;
}

int main() {
	
	cin >> testCase;
	checkPrimeNumber();
	for(int i = 0; i < testCase; i++){
		m.clear();
		cin >> number;
		divideNumber(number);
		sort(divideNum.begin(), divideNum.end());
		cout << solve() << "\n";
	}
	
	
	return 0;
}