[백트랙킹]백준2023번 신기한 소수

백준2023

앞자리부터 한 자리씩 뽑아나가며 현재까지 만들어지는 수가 소수인지 판별하면 된다.

구현은 복잡하지는 않았다.

처음 사용했던 방법은

1. 에라토스테네스의 체를 사용해 최대 target까지의 소수를 모두 찾아낸다. (target = 10 ^ N)
2. 한 자리씩 선택하며 조합된 수가 소수라면 백트랙킹을 진행한다.

였다.

에라토스테네스의 체에 대한 설명은 에라토스테네스의 체 를 참고하면 된다.

// 에라토스테네스의 체 
vector<int> all_num(num2-num1+1,0);

    for(int i=num1; i<= num2; i++){ 
        if(all_num[i-num1]==0){
        for(int j = 2; j <= sqrt(i) ; j++){
            if(i%j==0){
               all_num[i-num1] = 1; 
               break;
            }
         }
        }
    }

이 방법을 사용한 뒤에는 백트랙킹을 통해 가능한 모든 조합을 확인하며 조합되는 수가 소수인지만 확인하면 된다.

단, 이 방법(에라토스테네스의 체)을 사용하면 메모리 초과가 발생하게 된다.

메모리 초과를 잡을 수 있는 방법을 검색해봤는데,

1. 첫 자리에는 무조건 2 3 5 7 만 올 수 있다.

   왼쪽에서부터 한 자리도 소수여야 하기 때문이다.

2. 메모리 제한이 4MB 이기 때문에 만약 입력으로 8이 들어온다면 메모리 초과가 발생하게 된다.

   int 는 4 바이트 이기 때문에 메모리 제한이 4MB라면 int 형은 1,000,000 개 까지만 선언할 수 있다.

   bool 형은 1바이트 이기 때문에 4,000,000개까지만 가능한데, 문제에서는 N 이 8까지 들어온다고 했기 때문에 미리 에라토스테네스의 체로 구현하면 무조건 메모리 초과가 발생한다.

따라서 첫 자리는 2 3 5 7 안에서만 선택하도록 하고, 그 뒷자리도 자릿수가 늘어갈수록 경우의 수가 점점 줄어들기 때문에 그 때 그 때 에라토스테네스의 체를 수행해도 시간 초과가 발생하지 않는다.

#include <iostream>
#include <math.h>
#include <vector>
using namespace std; 

int N,target;
// bool isPrime[10000001]; 주석 해제 시 메모리 초과 발생
int num[4] = {2,3,5,7};
bool isUsed[10];
int arr[8];

bool checkPrime(int n){
    int tmp = 0;
    for(int i=0;i<n;i++){
        tmp += arr[i] * pow(10,n-(i+1));
    }
    // cout << tmp << endl;
    for(int i=2;i<=sqrt(tmp);i++){
        if(tmp%i==0) return false;
    }
    // if(!isPrime[tmp]) return true;

    return true;
}

void func(int n){
    if(n==N){
        int tmp = 0;
        for(int i=0;i<N;i++){
            tmp += arr[i] * pow(10,n-(i+1));
        }
        cout << tmp << "\n";
        return;
    }
    if(n==0){
        for(int i=0;i<4;i++){
            arr[n] = num[i];
            func(n+1);
        }
    }
    else{    
        for(int i=0;i<10;i++){
            if(1){
                arr[n] = i;
                if(checkPrime(n+1)){
                    isUsed[i] = true;
                    func(n+1);
                    isUsed[i] = false;
                }

            }
        }
    }
    return;
}
int main(){
    cin >> N;
    target = pow(10,N);
    // isPrime[0] = true;
    // isPrime[1] = true;
    // for(int i=2;i<=target;i++){
    //     for(int j=2;j<=sqrt(i);j++){
    //         if(i%j==0){
    //             isPrime[i] = true;
    //         }
    //     }
    // }
    func(0);
    
}