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

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

2023번: 신기한 소수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;

bool check(int n) //소수 체크
{
    for(int i=2; i*i<=n; i++)
    {
        if(!(n%i)) return 0;
    }
    return 1;
}

void dfs(int n, int len)
{
    if(len == N)
    {
        cout << n << "\n";
        return;
    }

    for(int i=1; i<10; i+=2) //짝수는 소수가 아니므로 패스
    {
        if(!check(n*10+i)) continue;
        dfs(n*10+i, len+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    dfs(2, 1); //맨 앞자리가 소수 2, 3, 5, 7
    dfs(3, 1);
    dfs(5, 1);
    dfs(7, 1);

    return 0;
}

 

맨 처음 오는 숫자는 무조건 소수여야 한다.

1~9까지 중에 소수는 2, 3, 5, 7이므로 해당 숫자들을 베이스로 재귀 탐색을 돌려준다.

이때 총 길이가 N이 되어야 하므로 길이를 체크할 변수를 하나 넘긴다.

1개부터 시작이므로 1을 넘겨준다.

 

dfs를 돌며 현재 입력받은 소수인 n을 10을 곱하여 자릿수를 확장하고 또 해당 값에 1~9까지를 더한 값이 소수인지를 체크해준다.

자릿수를 확장하고 더할 때마다 소수를 체크해야하므로 소수 체크를 위한 함수를 따로 작성한다.

 

소수가 맞다면 다시 자릿수 확장을 위해 변한 값과 사이즈를 + 1하여 넘겨준다.

이를 반복하여 사이즈가 N에 도달하면 만들어진 N사이즈 숫자를 출력해준다.