[boj] 백준 2023 신기한 소수 - DFS

[문제]

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

2023번: 신기한 소수

 

[풀이]

dfs로 풀 수 있다. 왼쪽에서 1번째, 2번째 ... n번째 자리까지의 수가 모두 소수여야 하므로 처음 올 수 있는 수는 소수인 2, 3, 5, 7 밖에 없다. 이 수들에 대해서 짝수는 소수가 아니므로 홀수를 대상으로만 수를 덧붙여 소수 판별을 해주고, 소수인 수들에 대해서 n자리가 될 때까지 반복한다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace::std;

int n;

bool check(int num){
    //소수인지 판별
    if(num==0 || num==1)
        return false;
    for(int i=2; i<num; i++){
        if(num%i==0)
            return false;
    }
    return true;
}

void solve(int s, int depth){
    if(depth==n){
        cout << s << endl;
        return;
    }

    for(int i=1; i<=9; i+=2){ // 홀수만
        if(check(s*10+i))
            solve(s*10+i, depth+1);
    }
}


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

    cin >> n;
    solve(2, 1);
    solve(3, 1);
    solve(5, 1);
    solve(7, 1);

}