[백준 2023] 신기한 소수 C++

문제

백준 2023 신기한 소수 C++

2023번: 신기한 소수

풀이

백트래킹을 활용합니다.

1. 0자리부터 시작합니다.

2. 현재 숫자에 1~9까지 숫자를 뒤에 붙여가며 소수인지 판별합니다.

2-1. 소수라면 dfs를 재귀호출 합니다. 이 때 수와 자리수를 갱신해줍니다.

3. 현재 수가 N자리 이면 수를 출력하고 함수를 종료합니다.

소스 코드

#include <iostream>
#include <cmath>
using namespace std;
 
int N;
// 소수 판별
bool isPrime(int num) {
    if (num == 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
 
// 백트래킹
void dfs(int num, int cnt) {
    // 자리수가 N이면 출력
    if (cnt == N) {
        cout << num << '\n';
        return;
    }
    // 1부터 9까지 붙여주면서 next가 소수면 dfs실행
    for (int i = 1; i <= 9; i++) {
        int next = num * 10 + i;
        if (isPrime(next)) {
            dfs(next, cnt + 1);
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    dfs(0, 0);
    return 0;
}