[2023] 신기한 소수

✔ 신기한 소수

[백준 2023]

문제 분석하기

DFS는 재귀 함수의 형태를 띄고 있으므로 재귀 함수에 자릿수 개념을 붙이고 문제 조건에 맞도록 가지치기하여 문제에 접근

손으로 풀어보기

1. 자릿수가 1개인 소수는 2, 3, 5, 7이므로 이 수부터 탐색을 시작
   • 소수가 아닌 4, 6, 8, 9를 제외한 가지치기 방식을 적용
2. 이어서 자릿수가 2개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘림
   • 단, a가 짝수인 경우는 항상 2를 약수로 가지고 있으므로 가지치기로 a가 짝수인 경우를 제외함
3. 이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력

예) N = 4

자릿수 1개	자릿수 2개	자릿수 3개	자릿수 4개	신기한 소수
2 3 5 7	1 3 5 7 9			21은 소수가 아님, 탐색 중단
2 3 5 7	1 3 5 7 9	1 3 5 7 9		231은 소수가 아님, 탐색 중단
2 3 5 7	1 3 5 7 9	1 3 5 7 9	1 3 5 7 9	2331은 소수가 아님, 탐색 중단 2333은 소수, N이 4이므로 출력 2335는 소수가 아님, 탐색 중단 2337은 소수가 아님, 탐색 중단 2339는 소수, N이 4이므로 출력

슈도코드 작성하기

N(자릿수)
DFS(2, 1)
DFS(3, 1)
DFS(5, 1)
DFS(7, 1)

DFS(숫자, 자릿수) {
    if(자릿수 == N) {
        if(소수)
            수 출력하기
        탐색 종료하기
    }
    for(1 ~ 9 반복하기) {
        if(뒤에 붙는 수가 홀수이면서 소수일 때) {
            DFS(현재 수 * 10 + i, 자릿수 + 1)
        }
    }
}

for(2 ~ 현재 수 / 2 반복하기) {
    if(나머지가 0이면) 
        return 소수가 아님
}
return 소수임

코드 구현하기

/**
 * 2023) 신기한_소수
 */
public class D024_2023 {
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(자릿수)
        N = sc.nextInt();
        // 일의 자리 소수는 2, 3, 5, 7이므로 4개 수에서만 시작
        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }

    // DFS
    public static void DFS(int number, int jarisu) {
        if (jarisu == N) {
            if (isPrime(number)) {
                System.out.println(number);
            }
            return;
        }
        for (int i = 1; i < 10; i++) {
            // 뒤에 붙는 수가 홀수이면서 소수일 때
            if (i % 2 == 0) {
                continue;
            }
            if (isPrime(number * 10 + i)) {
                // 자릿수를 1씩 늘리면서 DFS 실행
                DFS(number * 10 + i, jarisu + 1);
            }
        }
    }

    // 소수 구하기
    public static boolean isPrime(int num) {
        // 약수가 1과 자기 자신일 경우에만 소수
        for (int i = 2; i <= num / 2; i++)
            if (num % i == 0)
                return false;
        return true;
    }
}