문제

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

---

풀이

메모리 초과 (4MB 제한)

메모리가 최대 4MB 제한이므로, 배열 크기를 최대 10^8 = 1억으로 잡으면 메모리 초과가 날 수밖에 없다. int 타입 기준으로 1억개의 원소를 배열에 저장하려면, 4B * 10^8 = 400MB의 메모리 공간이 필요하기 때문이다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map> 
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N; 

void input() {
	cin >> N; // 자리 수 
}

bool isPrimeNumber(int x) {
	if (x < 2) // 소수의 정의에서 벗어난 수들은 예외 처리
		return false;

	// 2부터 x의 제곱근까지 모든 수를 확인하며
	for (int i = 2; i <= (int)sqrt(x); i++) {
		// x가 해당 수로 나누어 떨어진다면 
		if (x % i == 0) {
			// i와 그에 대칭인 수는 모두 x의 약수이고, x는 소수가 아님.
			return false; 
		}
	}

	return true;
}

void solution() {
	// N자리 자연수의 최소, 최대 값 구하기 
	int minVal = 0, maxVal = 0;
	for(int i = N - 1; i >= 0; i--){
		int square = pow(10, i);
		minVal += 1 * square;
		maxVal += 9 * square;
	}

	// N자리 자연수 중에서 소수를 모두 찾는다.
	vector<bool> prime(maxVal + 1, true);
	
	for (int i = minVal; i <= maxVal; i++) {
		if (prime[i]) {
			// i 자신을 제외한 i의 배수 모두 지우기
			for(int j = 2 * i; j <= maxVal; j += i){
				prime[j] = false;
			}
		}
	}

	// 그 소수들 중에서 1~N자리까지 모두 소수인 숫자를 찾는다. 
	vector<int> answer;
	for (int i = minVal; i <= maxVal; i++) {
		if (prime[i]) {
			bool isAllPrime = true;
			
			for(int j = 0; j < N; j++){
				int temp = i / pow(10, j);
				if(!isPrimeNumber(temp)) {
					isAllPrime = false;
					break;
				}
			}

			if(isAllPrime) answer.push_back(i);
		}
	}

	for(auto e: answer){
		cout << e << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	input(); 
	solution(); 

	return 0; 
}

시간 초과

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map> 
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N; 

void input() {
	cin >> N; // 자리 수 
}

bool isPrimeNumber(int x) {
	if (x < 2) return false;

	for (int i = 2; i <= (int)sqrt(x); i++) {
		if (x % i == 0) return false; 
	}

	return true;
}

void solution() {
	// N자리 자연수의 최소, 최대 값 구하기 
	int minVal = 0, maxVal = 0;
	for(int i = N - 1; i >= 0; i--){
		int square = pow(10, i);
		minVal += 1 * square;
		maxVal += 9 * square;
	}

	vector<int> answer; 
	for (int i = minVal; i <= maxVal; i++) {
		// N자리 자연수 중에서 소수를 찾는다. 
		if(isPrimeNumber(i)) {
			bool isAllPrime = true;

			for(int j = 0; j < N; j++){
				int temp = i / pow(10, j);
				if(!isPrimeNumber(temp)) {
					isAllPrime = false;
					break;
				}
			}

			// 1~N자리 숫자까지 모두 소수이면 정답 
			if(isAllPrime) answer.push_back(i);
		}
	}

	for(int e: answer){
		cout << e << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	input(); 
	solution(); 

	return 0; 
}

정답 코드

이 문제에서 중요하게 알아차려야 하는 점은, 왼쪽부터 1자리 수도 소수여야 한다는 것이다. 그런데 한 자리 소수는 2, 3, 5, 7 이 4가지밖에 없다!

따라서, 왼쪽에서 가장 첫번째 자리 수는 2, 3, 5, 7 중에 하나로 고정한다. 그리고 그 아래의 자리 수에는 '홀수'만 더해나가면서 1~N자리까지 모두 소수인지 검사한다.

홀수만 더하는 이유는 짝수를 더해버리면 1~N자리 숫자 중에 소수가 아닌 게 반드시 포함될 수밖에 없기 때문이다.

그리고 dfs 함수의 인자로 (현재 숫자, 자리 수) 를 넘겨주면서 재귀적으로 경우의 수를 구하다가, 자리 수가 0이 되면 백트래킹 하면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map> 
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N;
int prime[4] = {2, 3, 5, 7};

void input() {
	cin >> N; // 자리 수 
}

bool isPrime(int x) {
	if (x < 2) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

void dfs(int num, int digit) {
	if (digit == 0)
		cout << num << "\n";
	
	for(int i = 1; i < 10; i += 2){
		int temp = num * 10 + i;
		if(isPrime(temp)){
			dfs(temp, digit - 1);
		}
	}
}

void solution() {
	for(int i = 0; i < 4; i++){
		dfs(prime[i], N - 1);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	input(); 
	solution(); 

	return 0; 
}

이 문제는 있는 그대로 구현하면 메모리 초과, 시간 초과 나는 문제이다.

문제의 조건을 유심히 생각해보고, 가장 효율적으로 정답을 구할 수 있는 방법을 고안해야 한다!!