[BOJ] 백준 2023번 : 신기한 소수 자바 (JAVA) 1

1. 문제

백준 2023번 신기한 소수 - https://www.acmicpc.net/problem/2023

✅ 알고리즘 분류 - 백트래킹, 정수론

🥇 난이도 - Gold 5

2. 풀이

이 문제의 핵심은 자릿수를 하나씩 덧붙여가는 과정에서 수 대부분을 쉽게 가지 칠 수 있다는 것입니다.

우선 몇 자릿수든 신기한 소수가 되려면 왼쪽부터 1자리 숫자가 소수여야 합니다.

즉 신기한 소수의 첫째 자리 수는 소수인 2,3,5,7 중의 하나이고 이 경우에만 다음 자릿수를 더해주면 됩니다.

첫째 자리 수 2에 0부터 9까지 다음 자릿수를 더해주는 경우 20,21,22,24,25,26,27,28 는 소수가 아니므로 다음 단계로 진행하지 않고 소수인 23과 29의 경우에만 다음 자릿수를 더해줍니다.

이는 나머지 3,5,7의 경우에도 같게 진행합니다.

이런 방식으로 N의 자리까지 자릿수를 덧붙여가고 어떤 수가 N자리에 도달하면 최종적으로 N자리 수가 소수인지 판별하고 만약 소수이면 신기한 소수일 수밖에 없으므로 해당 값을 출력시키면 됩니다.

3. 코드

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

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        getResult(0,n);
        System.out.println(sb);
    }

    public static void getResult(int output, int n) {
        if (n == 0) {
            if (isPrime(output)) sb.append(output).append("\n");
            return;
        }
        for (int i=0; i<10; i++) {
            int next = output*10+i;
            if (isPrime(next)) getResult(next, n-1);
        }
    }

    public static boolean isPrime(int num) {
        if (num < 2) return false;

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

}

4. 결과

5. 풀이 과정

일단 소수 문제여서 에라토스테네스의 체가 가장 먼저 떠올랐었는데 이 문제는 메모리 제한을 보니 4MB밖에 되지 않았습니다.

에라토스테네스의 체를 사용하지 못한다면 어떤 수를 소수인지 판별하는 데 있어 걸리는 시간은 log N이고, N개의 숫자에 대해 소수 판별을 진행하면 N log N이 걸리게 됩니다.

N이 최대 8자리 숫자가 될 수 있어서 N log N의 방식으로 풀면 시간제한인 2초를 초과하게 됩니다.

다른 방법을 생각해 보던 중 N이 몇이든 신기한 소수의 첫째 자릿수는 항상 소수여야 한다는 사실을 알게 되었고 재귀를 통해 신기한 소수가 될 가능성이 있는 경우에만 자릿수를 늘리는 방법을 생각하게 되었습니다.