[BOJ][Java] 2023번 신기한 소수

문제 설명

 

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

 

 

이번 문제는 N의 자리의 숫자 중 문제의 조건에 만족하는 소수를 출력하는 문제이다.

먼저 문제의 조건을 보면 7331 이라는 소수는 맨 앞인 7, 두 번째 자리까지인 73, 세 번째 자리까지인 733, 전체 7331 모두 소수라는 특징을 가지고 있다.

 

자기 자신과 1을 제외하고는 나누어지지 않는다는 소수의 특징을 보면 

N이 몇이든 맨 앞자리의 수는 2,3,5,7 이 되어야 한다.

그다음 숫자부터는 1,3,5,7,9 중 골라야 한다.

 

따라서 처음에는 2,3,5,7 중에서 그다음에는 1,3,5,7,9 중에서 골라 한 자리씩 추가될 때마다

소수인지 아닌지를 미리 확인하면서 가지치기를 하면 시간 안에 풀 수 있다.

하지만 처음부터 1,2,3,5,7,9 중에서 확인하면서 가지치기를 해도 N의 값이 크지 않기 때문에

시간복잡도 내에 풀 수 있기에 좀 더 편리하게 구현하는 방식을 택했다.

또한 소수인지 판별하는 방식 또한 N이 더 크거나 시간을 줄이고 싶다면

에라토스테네스의 체를 활용하여 시간을 더욱 단축시킬 수 있다.

 

 

package boj;

import java.util.Scanner;

public class BOJ2023 {

    static int[] dig = {1,2,3,5,7,9};
    static StringBuilder sb = new StringBuilder();
    static int N;

    public static void main(String[] args) throws Exception{

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        dfs(0,0);

        System.out.println(sb);

    }

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

        for(int i: dig){
            int temp = num*10 + i;
            if(isPrime(temp)){
                dfs(n+1, temp);
            }
        }
    }

    static boolean isPrime(int num){
        if(num == 1) return false;
        if(num == 2) return true;

        for(int i = 2; i< Math.sqrt(num) + 1; i++){
            if(num%i == 0) return false;
        }
        return true;
    }
}