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

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

이 문제는 dfs를 이용하여 풀 수 있습니다. 이 문제는 수의 자리수가 매우 크기 때문에 에라토스테네스의 체 방식으로 소수를 구한 후 해당 범위를 체크하면 시간 초과 및 메모리 초과가 발생합니다. 따라서 시간과 메모리를 적게 사용하는 방식으로 풀어야 합니다.

dfs와 소수의 특징을 이용하면 시간 초과 및 메모리 초과를 방지할 수 있습니다. 모든 소수를 체크하는 것이 아닌, 한 자리의 소수를 각 자리수에 추가하면서 전체 수가 소수인지를 체크하는 것이 더 효과적입니다. 이 때 에라토스테네스의 체를 통해 모든 소수를 저장하는 것이 아니라 2부터 num/2까지 나누었을 때의 나머지가 모두 0이 아닌 경우 소수로 체크하는 것이 메모리 초과를 방지할 수 있습니다. 각 자리수를 dfs로 탐색하면서 홀수(짝수를 추가할 경우 무조건 2의 배수이기 때문에 소수가 될 수 없음)를 추가하면서 추가된 수가 소수인지를 탐색합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

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

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dfs(2,1);
        dfs(3,1);
        dfs(5,1);
        dfs(7,1);
        System.out.println(sb);
    }

    static void dfs(int val, int dpt){
        if(dpt == N){
            sb.append(val).append("\n");
            return;
        }

        for(int i=1;i<=9;i+=2){
            int next = val*10 + i;
            if(isPrime(next)) dfs(next, dpt+1);
        }
    }

    static boolean isPrime(int num){
        for(int i=2;i<=num/2;i++){
            if(num%i == 0) return false;
        }
        return true;
    }
}