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

문제

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

 

풀이

모든 경우를 탐색하면 무조건 시간초과난다.

소수의 특징을 잘 파악하여 효율적으로 푸는 방법을 생각해 내야 한다.

 

맨 앞자리 숫자부터 차례로 모두 소수여야 하므로, 맨 앞자리는 소수인 2,3,5,7로 지정하고, 이후 자리수를 하나씩 늘려가며 소수인지 확인하는 방식으로 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Boj_2023_신기한소수 {

    static int n;

    static void dfs(int num, int index){
        if(index == n){ // 백트래킹
            // n자리 모두 구하면
            if(checkPrime(num)){ // 소수인 경우 출력
                System.out.println(num);
            }
        }

        for(int i = 0; i < 10; i++){
            if(i % 2 == 0){ // 짝수면 무시,
                continue;
            }else{
                if(checkPrime(num*10 + i)){ // 소수인 경우
                    dfs((num*10 + i), index +1);
                }
            }
        }



    }
    public static boolean checkPrime(int num){ // 소수인지 확인

        for(int j = 2; j <= num/2; j++){
            if(num % j == 0){
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine()); // 숫자 자리수

        // 7331 = 7, 73, 733, 7331


        // 한자리 소수 - 2, 3, 5, 7
        // 소수 가능성 - 1, 3, 5, 7, 9 (홀수)
        // -> 마지막 자리가 짝수이면 무조건 2로 나누어 떨어짐
        int[] targetOne = {2, 3, 5, 7};

        for(int i = 0; i < 4; i++) { // 첫번째 자리 수 지정(소수)
            dfs(targetOne[i], 1);
        }


    }
}