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

문제

분석

N자리 수를 입력하면 N자리 신기한 소수를 모두 출력하는 문제.

N자리 신기한 소수란 왼쪽부터 1자리, 2자리, ..., N자리 수 모두 소수인 수를 말한다. 예를들어 7331은 1자리 수 7도 소수, 2자리 수 73도 소수, 3자리 수 733도 소수, 4자리 수 7331도 소수 이므로 신기한 소수다.  참고로 N의 범위는 1<=N<=8이다.

 

N자리 신기한 소수가 되려면 여러 단계를 모두 통과해야 한다. 1자리 수도 소수이어야 하고 2자리 수도 소수 ,... N자리 수도 소수이어야 한다. 만약 어느 한 곳에서라도 소수가 아니면 그 수는 신기한 소수가 아니므로 다른 수를 찾는다. 마치 이 모습은 DFS로 각 자리 수가 소수인지 판별하고 맞으면 더 깊이 들어가고 아니면 나오는 모습과 유사하다. 그래서 DFS를 이용해서 문제를 풀었다. 

 

출력 결과는 오름차순으로 출력해야하기 때문에 작은 숫자부터 시작해서 숫자가 커지도록 반목문을 사용하였다.

그리고 소수를 판별하는 알고리즘은 따로 메서드로 구현하였다. dfs 메서드에서 매개변수는 숫자를 받는다. 처음 시작할 때에는 1자리 수를 받지만 깊이 들어갈 수록 현재 자리수 + 1이 된다. 그리고 만약 수가 소수가 아니라면 return하여 다른 수를 찾는다. 소수이면서 길이가 입력으로 주었던 수와 같으면 그때 StringBuilder를 이용해서 문자열을 저장한다.

 

 

소스코드

import java.util.Scanner;

public class 신기한소수_024 {

    static StringBuilder sb = new StringBuilder();
    static int N;

    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;
    }

    public static void dfs(String str) {
        if (!isPrime(Integer.parseInt(str))) return;

        if (str.length() == N) {
            sb.append(str + "\n");
            return;
        }
        else {
            for (int i=0; i<=9; i++) {
                dfs(str + i);
            }
        }
    }

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

        for (int i=0; i<=9; i++) {
            dfs(String.valueOf(i));
        }

        System.out.println(sb.toString());
    }
}

결과