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

 

 

N자리의 정수 중, 신기한 소수를 구하는 문제이다.

신기한 소수란, 정수의 가장 앞에서부터 1자리, 2자리, 3자리 .... N자리까지의 숫자가 모두 소수인 수이다.

 

예를 들어, 7331의 경우 앞에서부터 1자리인 7도 소수이며, 앞에서부터 2자리인 73도 소수이고, 앞에서부터 3자리인 733과 앞에서부터 4자리인 7331도 소수이다.

 

이러한 수를 모두 출력하면 된다.

 

문제 풀이

이 문제의 규칙을 한 번 생각해보자.

 

7331처럼, 신기한 소수가 되는 수는 7, 73, 733, 7331 이 모두 소수이다.

 

4개의 숫자를 생각해보면, 73은 7의 뒤에 한자리의 숫자가 더해진 형태이며 733은 73의 뒤에 한자리의 숫자가 더해진 형태이다. 7331또한, 733뒤에 한자리의 숫자가 더해진 형태이다.

 

즉, N자리의 신기한 소수는 (N - 1)자리의 신기한 소수의 뒤에 한 자리의 숫자가 더해진 형태가 된다.

이를 기반으로 1자리 수 부터 탐색을 해보자.

 

1자리의 신기한 소수는 2, 3, 5, 7이 있다.

 

2자리의 신기한 수는 1자리의 신기한 수의 뒤에 1자리의 숫자를 더한 형태였다.

그렇다면, 21, 22, 23, 24, 25, 26, 27,28, 29, 31, 32, 33, 34, 35, 36,37, 38, 39 .... 등의 숫자들이 신기한 수의 후보가 될 수 있다. 이 수들 중에 소수인 수가 있다면 해당 수는 신기한 소수일 것이다.

 

그렇다면, 해당 숫자들을 대상으로 소수 판별을 해야한다.

소수가 되기 위해선 첫 번째로, 가장 마지막 자리가 짝수여서는 안된다.

그러므로, 22, 24, 26, 28 ...등은 후보에서 제외할 수 있다.

 

남은 숫자 21, 23, 25, 27, 29, 31, 33 등의 숫자를 대상으로 소수 판별을 해보자.

소수를 판별하는 방법은 간단하다. N이라는 숫자가 있을 때, 2~sqrt(N)까지 반복문을 돌면서 N을 해당 수로 나누어보면 된다. 

 

예를 들어, 15가 소수인지 판별하고 싶다면 2~sqrt(15)까지의 정수에 대해 15를 나누었을 때, 나머지가 0이되는 경우가 있는지를 탐색하면 된다.

 

15 % 2 = 1

15 % 3 = 0

 

=> 15가 3으로 나누어지므로, 3이라는 약수가 존재함을 알 수 있다. 이로 인해, 15는 소수가 아님을 알 수 있다.

 

이렇게, 신기한 수의 뒤에 한자리 수 하나를 더하고 해당 수가 소수인지 아닌지를 판별하는 것을 한자리의 신기한 소수부터 시작해서 계속 반복하면 된다. 계속 반복하여 N자리의 소수를 모두 구한 뒤 출력하면 된다.

 

풀이 코드

int Digit = 0;
std::cin >> Digit;

먼저, 목표로 하는 자리 수를 입력받아준다.

std::priority_queue<int, std::vector<int>, std::greater<int>> Numbers;
for (int i = 2; i <= 9; i++)
{
    if (isPrimeNumber(i) == true)
    {
        Numbers.push(i);
    }
}

다음은 우선순위 큐에 한자리의 신기한 소수를 모두 삽입해준다.

isPrimeNumber는 해당 수가 소수인지 판별해주는 함수이다. 내부 구현 코드는 잠시 뒤에 보도록 하자.

if (Digit == 1)
{
    PrintAll(Numbers);
    return 0;
}

만약, 입력받은 자리수가 1이었다면, 그대로 모든 우선순위 큐의 모든 원소를 출력해주면 된다.

int Threshold = static_cast<int>(std::pow(10, Digit - 1));

이건, 미리 설정한 한계 수치이다.

예를 들어, 입력받은 자리수가 4라고 한다면 3자리 숫자에 대한 탐색이 끝나는 순간에 탐색을 멈추어야 한다.

 

3자리 숫자의 뒤에 한 자리 숫자를 더해 4자리 숫자를 구하고, 4자리 숫자의 뒤에 한자리 숫자를 더해 5자리 숫자를 구하는 방식이기 때문에, 현재 참조하는 숫자가 4자리 숫자라면 더이상 탐색을 진행할 필요가 없어진다.

 

Digit가 4인 경우에, Threshold는 1000이 되고, 현재 숫자가 1000보다 크거나 같다면 반복문을 종료하도록 할 것이다.\

while (true)
{
    int CurNum = Numbers.top();
    if (CurNum >= Threshold)
    {
        break;
    }

    Numbers.pop();

    CurNum *= 10;
    int NextNum = 0;

    for (int i = 0; i <= 9; i++)
    {
        if (i % 2 == 0)
        {
            continue;
        }

        NextNum = CurNum + i;

        if (isPrimeNumber(NextNum) == true)
        {
            Numbers.push(NextNum);
        }
    }
}

우선순위 큐의 원소중 최소값을 기준으로 Threshold 보다 큰지 작은지를 검사하였다.
최소값이 Threshold보다 더 작다면, 그대로 반복문을 종료해준다.

 

그렇지 않다면, 우선순위 큐의 최소값을 pop한 뒤, 해당 숫자의 뒤에 1을 더한 숫자를 모두 검사하여, 소수인 숫자는 다시 우선순위 큐에 삽입하도록 하였다.

 

2는 23, 29를 우선순위 큐에 삽입하며, 3은 31과 37을 우선순위 큐에 삽입한다. 5는 53과 59를 우선순위 큐에 삽입하며, 7은 71, 73, 79를 우선순위 큐에 삽입한다.

 

한 자리 수에 대한 탐색이 모두 끝나게 되면, 두 자리의 숫자를 대상으로 탐색을 하게 된다.

23은 233,239를 우선순위 큐에 삽입하고, 29는 293을 우선순위 큐에 삽입한다. 31은 311,313,317을 우선순위 큐에 삽입하며, 37은 37와 3789를 우선순위 큐에 삽입한다.

 

이 과정을 N자리 수의 신기한 소수를 모두 구할 때까지 반복하는 것이다.

PrintAll(Numbers);

return 0;

반복문이 끝난 뒤, 우선 순위 큐에 있는 모든 원소를 출력해주면 끝난다.

bool isPrimeNumber(int _Num)
{
    int NumSqrt = std::sqrt(_Num);

    for (int i = 2; i <= NumSqrt; i++)
    {
        if (_Num % i == 0)
        {
            return false;
        }
    }

    return true;
}

위의 코드는 소수를 판별하는 코드이다. 2~sqrt(N)까지 반복문을 돌며, _Num의 약수인 수가 있는지 확인하는 것이다.

void PrintAll(std::priority_queue<int, std::vector<int>, std::greater<int>>& _Numbers)
{
    while (_Numbers.size() > 0)
    {
        std::cout << _Numbers.top() << std::endl;
        _Numbers.pop();
    }
}

위 코드는 우선 순위 큐의 모든 원소를 출력하는 함수이다.

하나씩 pop해주며, top을 계속 출력하도록 하였다.

 

코드 전문

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

void PrintAll(std::priority_queue<int, std::vector<int>, std::greater<int>>& _Numbers)
{
    while (_Numbers.size() > 0)
    {
        std::cout << _Numbers.top() << std::endl;
        _Numbers.pop();
    }
}

bool isPrimeNumber(int _Num)
{
    int NumSqrt = std::sqrt(_Num);

    for (int i = 2; i <= NumSqrt; i++)
    {
        if (_Num % i == 0)
        {
            return false;
        }
    }

    return true;
}

int main()
{
    Init();

    int Digit = 0;
    std::cin >> Digit;

    std::priority_queue<int, std::vector<int>, std::greater<int>> Numbers;
    for (int i = 2; i <= 9; i++)
    {
        if (isPrimeNumber(i) == true)
        {
            Numbers.push(i);
        }
    }

    if (Digit == 1)
    {
        PrintAll(Numbers);
        return 0;
    }

    int Threshold = static_cast<int>(std::pow(10, Digit - 1));

    while (true)
    {
        int CurNum = Numbers.top();
        if (CurNum >= Threshold)
        {
            break;
        }

        Numbers.pop();

        CurNum *= 10;
        int NextNum = 0;

        for (int i = 0; i <= 9; i++)
        {
            if (i % 2 == 0)
            {
                continue;
            }

            NextNum = CurNum + i;

            if (isPrimeNumber(NextNum) == true)
            {
                Numbers.push(NextNum);
            }
        }
    }

    PrintAll(Numbers);

    return 0;
}