[백준][Java] 2023 - 신기한 소수

문제 정보

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

2023번: 신기한 소수

난이도 : G5

유형 : 재귀, 정수론, 소수판정, 백트래킹

---

문제 풀이

문제 메모리 조건을 때문에 미리 소수배열을 만들어 놓으면 메모리 초과가 뜰 것이다.

그래서 어떤 수가 소수인지 동적으로 판별하여야 한다.

 

풀이 방법  - 예시 - 5939)

첫번째 수가 소수이다. (5)  

-> 첫째둘째 수가 소수이다. (59)

-> 첫째둘째셋째 수가 소수이다. (593)

-> ... N자리까지 소수이다. (5939)

 

위처럼 왼쪽에서 오른쪽으로 수를 분리해서 그 수가 소수인지 판별하면 된다.

---

코드

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

public class Main {

    private int N;
    private StringBuilder sb;

    public boolean isPrime(int num) {
        if (num == 0 || num == 1) {
            return false;
        }

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

    public void backTracking(int depth, int num) {
        if (depth == N) {
            if (isPrime(num)) {
                sb.append(num).append('\n');
                return;
            }
        }

        for (int i = 1; i <= 9; i++) {
            if (isPrime(num * 10 + i)) {
                backTracking(depth + 1, num * 10 + i);
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        backTracking(0, 0);

        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}