[백준] 2023번 신기한 소수

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

2023번: 신기한 소수

문제는 어렵지 않다. 하지만 처음 두 번의 제출은 시간초과로 실패했다.

가장 처음 제출한 코드는

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

int n;
vector<int> v;
set<int> answer;
int number;


void permutation(int num, vector<int> result) {
	if (num == n) {
		bool isAllPrime = true;
		for (int i = 0; i < n; i++) {
			number = 0;
			for (int j = 0; j <= i; j++) {
				number += (result[j] * pow(10, i - j));
			}
			if (number == 1)
				isAllPrime = false;
			for (int j = 2; j <= sqrt(number); j++) {
				if (number % j == 0) {
					isAllPrime = false;
					break;
				}
			}
		}

		if (isAllPrime) {
			number = 0;
			for (int i = 0; i < n; i++) {
				number += (result[i] * pow(10, n - 1 - i));
			}
			answer.insert(number);
		}
		return;
	}
	for (int i = 1; i <= 9; i++) {
		result[num] = i;
		permutation(num + 1, result);
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	v = vector<int>(n);
	permutation(0, vector<int>(n));
	for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
		cout << *iter << '\n';
	}
	return 0;
}

이거였다. 그런데 이것의 문제는 일단 모든 가능한 n자리 수를 다 구하고 그 다음에 그것이 신기한 소수인지 확인했다.

그리고 신기한 소수인지 확인할 때도 예를 들어 n이 4일 때 6666이라는 절대 신기한 소수가 될 수 없는 수라도 8가 소수인지 확인, 88아 소수인지 확인, 889이 소수인지 확인, 8888이 소수인지 확인을 해주었다.  너무나도 비효율적이라는 것을 깨달았다. 애초에 8이 소수가 아닐 때부터 얘는 신기한 소수의 대상에서 제외를 해줘야 하는데 말이다.

 

그래서 두번째 코드는 이렇게 수정하였다.

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

int n;
vector<int> v;
set<int> answer;
int number;


void permutation(int num, vector<int> result) {
	if (num == n) {
		bool isAllPrime = true;
		for (int i = 0; i < n; i++) {
			if (!isAllPrime)
				break;
			number = 0;
			for (int j = 0; j <= i; j++) {
				number += (result[j] * pow(10, i - j));
			}
			if (number == 1)
				isAllPrime = false;
			for (int j = 2; j <= sqrt(number); j++) {
				if (number % j == 0) {
					isAllPrime = false;
					break;
				}
			}
		}

		if (isAllPrime) {
			number = 0;
			for (int i = 0; i < n; i++) {
				number += (result[i] * pow(10, n - 1 - i));
			}
			answer.insert(number);
		}
		return;
	}
	for (int i = 1; i <= 9; i++) {
		result[num] = i;
		permutation(num + 1, result);
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	v = vector<int>(n);
	permutation(0, vector<int>(n));
	for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
		cout << *iter << '\n';
	}
	return 0;
}

 일단 모든 가능한 n자리의 수를 다 구하는 것까지는 똑같았고 n이 4일 때 8888이면 처음 8을 확인해보고 소수가 아니면 그냥 for문을 더 이상 돌지 않고 끝내었다. 하지만 이것도 시간초과가 났다.

 

그래서 세 번째에는 애초에 신기한 소수가 될 수 없다면 재귀함수를 호출하지 않고 가지를 쳐버렸다.

이게 바로 백트래킹인데 나는 바보짓을 했다는 것을 스스로 알아내었다.

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

int n;
vector<int> v;
set<int> answer;
int number;
bool flag;

void permutation(int num, vector<int> result) {
	if (num == n) {
		number = 0;
		flag = true;
		for (int i = 0; i < n; i++) {
			number += (result[i] * pow(10, n - 1 - i));
		}
		answer.insert(number);
		return;
	}
	for (int i = 1; i <= 9; i++) {
		result[num] = i;
		number = 0;
		flag = true;
		for (int j = 0; j <= num; j++) {
			number += (result[j] * pow(10, num - j));
		}
		if (number == 1)
			flag = false;
		for (int j = 2; j <= sqrt(number); j++) {
			if (number % j == 0) {
				flag = false;
				break;
			}
		}
	
		if(flag)
			permutation(num + 1, result);
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	v = vector<int>(n);
	permutation(0, vector<int>(n));
	for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
		cout << *iter << '\n';
	}
	return 0;
}

 이렇게 했더니 0ms로 통과했다.