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

문제: 신기한 소수 (백준 2023번)

문제 분석

문제 개요:
길이가 nn인 신기한 소수를 찾는 문제로,
신기한 소수란 왼쪽부터 한 자리씩 늘려가며 만들어지는 모든 접두사가 소수인 수이다.
예를 들어, 73317331의 경우, 77, 7373, 733733, 73317331 모두 소수여야 한다.

접근 방법:

1. 백트래킹(Backtracking) 사용:
   • 재귀를 통해 자릿수를 늘려가며 후보 숫자를 구성한다.
   • 각 단계마다 현재까지 구성된 숫자가 소수인지 판별하고, 소수가 아니면 더 이상 진행하지 않는다.
2. 소수 판별 함수:
   • 입력된 수가 소수인지 확인하기 위해 22부터 $\sqrt{num}$ 까지의 나눗셈으로 판별한다.
3. 문자열 활용:
   • 숫자를 문자열로 조작한 후, stoi 함수를 통해 정수로 변환하여 소수 여부를 확인한다.

---

전체 코드

#include <bits/stdc++.h>
using namespace std;

int n;
string s = ""; // 현재까지의 숫자 조합

// 소수 판별 함수: num이 소수이면 true 반환
bool IsPrime(int num)
{
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0) return false;
    }
    return true;
}

// 백트래킹 함수: depth는 현재 자릿수
void BackTacking(int depth)
{
    if (depth == n)
    {
        cout << s << '\n';
        return;
    }
    // '1'부터 '9'까지의 숫자를 시도
    for (char i = '1'; i <= '9'; i++)
    {
        s += i; // 현재 후보 숫자 추가
        // 현재까지의 숫자가 소수라면 다음 자릿수로 진행
        if (IsPrime(stoi(s)))
        {
            BackTacking(depth + 1);
        }
        s.pop_back(); // 후보 숫자 제거 후 다른 숫자 시도
    }
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    cin >> n;
    BackTacking(0);
}