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

🚀 문제 분석

• 목표: $N$자리의 숫자 중, 왼쪽부터 1자리, 2자리, ..., $N$자리가 모두 소수인 '신기한 소수'를 오름차순으로 출력합니다.
• 제약: $N \le 8$. 단순히 모든 $N$자리 숫자를 전수 조사하면 $10^8$번의 연산이 필요하여 시간 초과 위험이 큽니다.
• 전략: 앞에서부터 숫자를 붙여가며 소수일 때만 다음 자릿수로 넘어가는 백트래킹(Backtracking) 방식을 사용합니다.

💡 해결 전략: 가지치기(Pruning)를 활용한 탐색

모든 숫자를 다 보는 것이 아니라, '신기한 소수'의 가능성이 있는 가계도만 따라 내려가는 것이 핵심입니다.

1. 시작점 설정: 1자리 숫자 중 소수인 것은 2, 3, 5, 7입니다. 이 네 숫자가 가계도의 뿌리가 됩니다.
2. 자릿수 확장: 현재 소수인 수에 0~9를 붙여 새로운 수를 만듭니다.
3. 조건 검사: 새로 만든 수가 소수라면 다음 자릿수로 재귀 호출을 진행합니다. 소수가 아니라면 그 즉시 해당 경로를 포기(Pruning)합니다.
4. 종료 조건: 자릿수가 $N$에 도달하면 신기한 소수가 완성된 것이므로 출력 리스트에 담습니다.

💻 구현 코드 (Java)

import java.util.Scanner;

public class Main {
    static int N;
    static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        // 1자리 소수(2, 3, 5, 7)부터 탐색 시작
        backtrack(0, 0);
        System.out.print(sb.toString());
    }

    static void backtrack(int cur, int k) {
        // N자리에 도달하면 결과 추가
        if (k == N) {
            sb.append(cur).append("\n");
            return;
        }

        for (int i = 0; i < 10; i++) {
            // 자릿수 확장 (예: 2 -> 23)
            int next = cur * 10 + i;
            
            // 소수일 때만 가지를 뻗음 (가지치기)
            if (isPrime(next)) {
                backtrack(next, k + 1);
            }
        }
    }

    // 소수 판별 최적화: sqrt(n)까지만 확인
    static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

🧐 기술적 고찰

• 탐색 범위의 비약적 감소: $N=8$일 때, 1억 개의 숫자를 검사하는 대신 백트래킹을 쓰면 소수의 계보를 잇는 극소수의 경로만 탐색하므로 2초라는 제한 시간 내에 아주 여유롭게 통과할 수 있습니다.
• 소수 판별 알고리즘: 에라토스테네스의 체를 쓰기엔 숫자의 범위(최대 99,999,999)가 너무 크고 메모리 제한이 걸릴 수 있습니다. 따라서 각 단계마다 $O(\sqrt{N})$의 판별법을 사용하는 것이 이 문제에선 더 효율적입니다.
• 재귀의 깊이: $N$이 최대 8이므로 재귀 호출로 인한 스택 오버플로우 걱정 없이 깔끔하게 구현 가능합니다.