백준 2023 신기한 소수 C++

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

2023번: 신기한 소수

---

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

---

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

---

1348ms코드가 나와서 , 시간 제한이 1초였으면 바로 틀렸습니다가 뜰 코드이고, 다른 분들의 코드를 보고 개선하였습니다.

먼저 제가 생각한 것은, N이 최소 1이니까 처음 시작은 한 자리 소수여야 합니다.

소수 중 한자리인 소수는 2,3,5,7,이고 DFS를 각각 2,3,5,7에 대해서 실행하였습니다.

 

먼저 소수를 판정하는 함수를 만들었습니다. 소수인 경우 1을, 소수가 아닌경우 -1을 반환하는 함수입니다.

int check_prime(int n){
   for(int i = 2;i*i<=n;i++){
       if(n%i == 0){
           return -1;
       }
   }
    
    return 1;
}

 

그리고 DFS함수인데, 함수의 인자로 문자열이 들어가고, 이 문자열이 N보다 큰 경우는 바로 return을 주었고,

1부터 9라는 숫자에 대해서, to_string으로 1부터 9를 문자열로 바꾸고 문자열에 이를 더해줍니다.

(새로 더해진 문자열을 Temp라고 하겠습니다.)

 

그리고 Temp에 대해서 DFS를 돌리고 문자열의 가장 뒤를 지워주었습니다. (백트래킹)

   for(int i = 1;i<=9;i++){
               string temp = str;
               str += to_string(i);
               dfs(temp);
               str.erase(str.size() - 1);
            }
        }

그리고 문자열의 길이가 N인 경우 이 문자열의 왼쪽부터 1자리,2자리,...N자리가 모두 소수인지 확인하였습니다.

 

 bool valid = false;
        string new_str = "";
        for(int i = 0;i<n;i++){
            new_str += str[i];
            int N = stoi(new_str);
            if(check_prime(N) == -1){
                valid = true;
                break;
            }
        }
        
        if(valid == false){
             cout << str << '\n';
        }
        return;
    }

 

만약 check_prime을 돌려서 -1이 나오면 소수가 아닌경우이므로 바로 탈출하고, 그 외의 경우에는 문자열을 출력하였습니다.

---

전체 소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

#define MAX 8
using namespace std;
int n;
int arr[MAX];
bool visited[MAX+2];

 
int check_prime(int n){
   for(int i = 2;i*i<=n;i++){
       if(n%i == 0){
           return -1;
       }
   }
    
    return 1;
}


void dfs(string str){
    if(str.size() >= n){ //N자리보다 크면 return
        if(str.size() > n){
            return;
        }
       
        bool valid = false;
        string new_str = "";
        for(int i = 0;i<n;i++){
            new_str += str[i];
            int N = stoi(new_str);
            if(check_prime(N) == -1){
                valid = true;
                break;
            }
        }
        
        if(valid == false){
             cout << str << '\n';
        }
        return;
    }
           
        for(int i = 1;i<=9;i++){
               string temp = str;
               str += to_string(i);
               dfs(temp);
               str.erase(str.size() - 1);
            }
        }
    
int main(void){
    cin >> n;

    dfs("2");
    dfs("3");
    dfs("5");
    dfs("7");
}

---

하지만 이 코드는 시간제한이 1초일 경우, 문제가 발생할 수 있는 코드입니다.

 

https://jaimemin.tistory.com/879

백준 2023번 신기한 소수

위의 블로그를 참조하였습니다.

 

1. 첫 번째로 등장할 수 있는 숫자는 2, 3, 5, 7 뿐입니다.

2. 이 후에는 홀수만 등장할 수 있습니다.

-> 짝수가 등장하면 신기한 소수의 조건을 만족하지 못합니다.

 

짝수가 등장하면 무조건 소수가 아닌 것이 보장되는 이유 ->

짝수는 모두 2의 배수이고, 2는 무조건 소수가 아니기 떄문

 

홀수인 숫자를 상대로만 DFS를 진행해야 시간 제한을 줄일 수 있었습니다.

---

   for(int i = 1;i<=9;i++){
               string temp = str;
               str += to_string(i);
               dfs(temp);
               str.erase(str.size() - 1);
            }
        }

위의 코드에서 홀수만 대상으로 DFS를 돌리게 바꾸었고,

   for(int i = 1;i<=9;i=i+2){
               string temp = str;
               str += to_string(i);
               dfs(temp);
               str.erase(str.size() - 1);
            }
        }

시간이 훨씬 줄어든 것을 확인할 수 있었습니다.!