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

Junseong·2022년 1월 3일

알고리즘

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

}