[Java] 신기한 소수 찾기_백준_2023

문제

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

2023번: 신기한 소수

 

풀이

재귀를 이용한 DFS와 자릿수 개념을 활용하는 문제입니다.

N자리 신기한 소수를 모두 출력해야되는데요.

신기한 소수란 왼쪽부터 1자리, 2자리, ..., N자리까지의 수가 모두 소수인 수를 말합니다.

 

그렇다면 왼쪽부터 1자리 수부터 시작해서 N자리 수까지 소수인지 확인해서 모두 소수였을 때 출력해주면 될 것 같습니다.

1자리에서는 소수가 될 수 있는 숫자는 2, 3, 5, 7입니다.

하지만 2자리 부터는 일의 자리수의 숫자가 11처럼 1이 올 수도 있습니다. 즉 2, 3, 5, 7이 아닌 다른 수로도 소수를 만들 수 있습니다.

그래도 확실한 건 짝수가 오면 2로 나눌 수 있기 때문에 소수가 될 수 없으므로 홀수일 경우에만 소수가 될 가능성이 있습니다.

 

마지막으로 출력할 때에는 오름차순으로 출력을 해야되는데 탐색방향을 숫자가 커지는 방향으로 탐색하기 때문에 따르 정렬을 할 필요는 없습니다.

소스코드

package 백준;
 
import java.util.Scanner;
 
/*
* N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력해라.
* 신기한 수란 왼쪽부터 1자리, 2자리, ..., N자리 수 모두 소수인 수를 의미한다.
*
* dfs을 이용하여 숫자를 오른쪽에 붙여나가다가 N자리 수가되면 출력
*
* */
public class 신기한소수_2023 {
    static int N;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
 
        dfs("2");
        dfs("3");
        dfs("5");
        dfs("7");
 
        System.out.println(sb);
    }
 
    public static void dfs(String num) {
        if (!isPrime(Integer.parseInt(num)))
            return;
 
        if (num.length() == N) {
            if (isPrime(Integer.parseInt(num)))
                sb.append(num).append("\n");
        } else {
            for (int i=1; i<=9; i+=2) {
                dfs(num + i);
            }
        }
    }
 
    public static boolean isPrime(int num) {
        if (num <= 1) return false;
 
        for (int i=2; i<=(int)Math.sqrt(num); i++) {
            if (num%i == 0)
                return false;
        }
 
        return true;
    }
}