백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)

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

아이디어

• N자리가 주어졌을때 모든자리 순회 > 1e9 > 시간초과
• 1의자리부터 소수일경우 넘어가고 넘어가는 순으로 하면어떨까
  • 그럼 BFS로 1의자리부터 N의자리까지 숫자 넣어서 체크해보자
    • 이때 BFS이니까 중복체크 필요
    • But, 큐 사용할경우 메모리 초과
      • dfs로 해결
• 에라토스테네스의 채 사용시 > 메모리 초과
  • 소수 확인 메소드로 사용

시간복잡도 계산

• DFS 시복도 : O(V+E) : 1e9
• 근데 1의 자리에서 4개밖에 없으니까 DFS 가능할듯

인트 계산

• 최대 8자리이므로, 인트 가능

코드

#include <iostream>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
 
bool decimalChk(int num) {
    // sqrt 까지 확인하면됨
    for(int i=2; i<=sqrt(num); i++) {
        if(num%i == 0) {
            return false;
        }
    }
    return true;
}
int N;
void dfs(int num) {
    if(to_string(num).size() == N) {
        cout << num << '\n';
        return;
    }
    
    for(int i=0; i<=9; i++) {
        string es = to_string(num) + to_string(i);
        int ei = stoi(es);
        if(decimalChk(ei) == 1) {
            dfs(ei);
        }
    }
}
 
 
int main() {
 
    cin >> N;
    
    for(int i=2; i<10; i++) {
        
        if(decimalChk(i) == 1) {
            dfs(i);
        }
    }
    
 
    return 0;
}
 

문제유형

• 그래프 탐색(BFS + DFS)