백준 2023: 신기한 소수

📃 문제: 백준 2023(신기한 소수)

 

2023번: 신기한 소수

 

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

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

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

 

 

🥇 난이도: 골드 5

 

 

😲 사용한 개념: DFS(깊이우선탐색), 소수 찾기 알고리즘

 

 ☝️ DFS란?

1️⃣ 탐색 시작 노드 정보를 스택에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드 정보를 스택에 삽입하고

pop연산과 동시에 방문 처리한다.
만일 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼낸다.(빈 스택 상태)
3️⃣ 아직 방문처리되지 않은 수 중 가장 작은 수를 push하여, 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

    ✌️ 소수 찾기 알고리즘

 

    이 문제에서는 2~N/2까지 순회하며 숫자를 나눴을 때 나머지가 0이 되는 경우가 있는지 검사하여 소수를 찾았다.

    추후에 소수 찾기를 더 효율적으로 할 수 있는 여러 소수 찾기 알고리즘에 대해 포스팅해보려고 한다.  

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드(c++ 사용)

#include <iostream>
#include <vector>
using namespace std;
int N;
//소수 판별 함수
bool isPrime(int number) {
    bool prime = true;
    for (int i = 2; i <= number / 2; i++) {
        if (number % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

void DFS(int num, int digit) {
    //자릿수 N이고, 소수인 경우 해당 숫자 출력
    if (digit == N && isPrime(num)) {
        cout << num << endl;
    }
    else {
        if (isPrime(num)) {
            for (int i = 1; i <= 9; i += 2) {
                int nextNum = num * 10 + i;
                //자릿수 하나 증가
                DFS(nextNum, digit+1);
            }
        }
        else return; 
    }
}

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

    cin >> N;
    //자릿수 1은 2, 3, 5, 7에 대해서만 수행
    int arr[4] = { 2,3,5,7 };
    for (int num : arr) {
        DFS(num, 1);
    }
    return 0;
}