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

백준의 신기한소수(2023) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제를 정답 간단하게 생각한다면 입력으로 주어지는 크기의 자릿수를 가지는 모든 숫자들을 다 구해서 소수인지 아닌지

   판단해서 소수가 맞다면 출력시키면 된다. 하지만, 이렇게 되면 시간이 너무 오래걸릴 것 같았다.(해보지는 않았음 !)

   그래서 본인은 한가지 제한만 더 주었다.

   문제에서 주어진 숫자인 7331 처럼 '7'도, '73', '733'도 소수여야 한다. 즉, 첫번째 자리 부터 소수여야 하기 때문에

   첫번째 자리에 올 수 있는 숫자는 2,3,5,7 밖에 없게 된다. 다른 숫자라면 첫 번째 자리가 숫자가 아니기 때문에 신기한 소수

   가 될 수 없기 때문이다. 따라서 첫 번째 자리는 2,3,5,7 에서만 시작하도록 설정해 주었다.

   이후에, 재귀를 통해서 모든 숫자들을 찾는 방식으로 구현했는데, 재귀에 들어가는 변수로는 (현재 숫자, 자릿수) 이렇게

   2개의 변수를 사용하였다.

   '현재숫자 * 10 + 이 다음에 올 숫자' 를 한 것이 소수라면 그 숫자를 재귀를 통해서 다시 호출해주는 식으로 구현하였다.

   하지만, 이 때 뒤에 더해지는 숫자는 홀수만 더하도록 하였다.

   뒤에 더해지는 숫자가 짝수라면 당연히 소수가 아니기 때문이다.

   ex) 첫번째 자리 = 7, 이 다음에 올 숫자 = 2  →  7 * 10 + 2 = 72 가 되어 소수가 절대 안됨 !

  

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N;
int First[] = { 2, 3, 5, 7 };
 
void Input()
{
    cin >> N;
}
 
bool SoSoo(int x)
{
    if (x < 2) return false;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
 
void DFS(int Fir, int Cnt)
{
    if (Cnt == 0)
    {
        cout << Fir << endl;
        return;
    }
 
    for (int i = 1; i < 10; i += 2)
    {
        int Tmp = Fir * 10 + i;
        if (SoSoo(Tmp) == true)
        {
            DFS(Tmp, Cnt - 1);
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < 4; i++)
    {
        DFS(First[i], N - 1);
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}