[BOJ] 2023 : 신기한 소수 - travelbeeee

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

---

[알고리즘풀이]

처음에는 에라토스테네스 체로 모든 소수를 구해놓고,

모든 N자리 숫자에 k에 대해 k를 뒤에서부터 자릿수를 날려가며 소수인지 아닌지 판별해서 출력했습니다.

하지만, 이 문제는 메모리 제한이 4MB로 극악의 메모리 제한을 가지고 있어, 메모리 제한 문제에 걸렸습니다.

 

문제에서 원하는 소수는 맨 뒤부터 자릿수를 날렸을 때, 모두 소수여야 되므로

맨 앞 자릿수가 2,3,5,7이어야 되고 나머지 자리도 1,3,5,7,9 중에 하나여야만 가능합니다.

이 특징을 이용하면 메모리 제한을 해결할 수 있습니다. 

 

백트레킹을 활용해서 모든 경우에 대해서 구했고, 중간에 소수가 아니면 백트레킹을 컷팅했습니다.

#include<iostream>
#include<vector>

using namespace std;

int n;
int p[4] = { 2,3,5,7 };
int o[5] = { 1,3,5,7,9 };

void bt(int s, int k) {
	if (k == n) {
		cout << s << '\n';
		return;
	}
	for (int i = 0; i < 5; i++) {
		bool check = false;
		s *= 10;
		s += o[i];
		for (int j = 2; j * j <= s; j++)
			if (s % j == 0){ // 소수가 아니라면 컷팅
				check = true; break;
			}
		if(!check)
			bt(s, k + 1);
		s -= o[i];
		s /= 10;
	}
	return;
}

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

	cin >> n;
	for (int i = 0; i < 4; i++) {
		bt(p[i], 1);
	}
	
	return 0;
}

---