[백준] BOJ 2023 신기한 소수 (골드 5)

문제

---

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

2023번: 신기한 소수

---

해설

---

---

1. 1~N자리 수 모두가 소수여야 한다.
2. 수의 맨 앞은 무조건 한자리 수 소수여야 신기한 소수의 조건에 맞다. 따라서 (2, 3, 5, 7) 첫번째 자리로 사용.
3. 이후 자리는 0 ~ 9중 어느 숫자가 와도 되지만, 이전 수에 새로운 수 0 ~ 9를 문자열로 더해준 후 해당 수가 소수인지 판단한다.
4. 만약 소수가 아니라면 신기한 소수가 될 수 없으므로 다음 케이스를 확인한다.
5. 소수라면 다음 자리 수에 0~9까지의 수를 문자열로 더해준 후 다시 소수인지 확인하는 과정을 반복한다.
6. 자리수가 N과 같다면 해당 수를 출력해준다.

---

import java.io.*;

import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BOJ2023.prob2023();
    }
}

class BOJ2023 {
    static  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    public static void prob2023() throws IOException {
        int N = Integer.parseInt(br.readLine());

        int[] primes = new int[]{2, 3, 5, 7};
        for (int i = 0; i < primes.length; i++) {
            interestPrime(N, 1, String.valueOf(primes[i]));
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void interestPrime(int N, int depth, String pre){
        if (!checkPrime(pre)) {
            return;
        }
        if (N == depth) {
            sb.append(pre).append("\n");
            return;
        }

        for (int i = 0; i <= 9; i++) {
            interestPrime(N, depth+1, (pre+i));
        }
    }
    private static boolean checkPrime(String cur){
        int val = Integer.valueOf(cur);
        for (int i = 2; i * i <= val; i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
    }
}

---

결론

---

예전부터 백트래킹 알고리즘에 대한 두려움이 있었는데 싸피에서 알고리즘 공부를 열심히 하다보니

이제는 익숙해진 분류인 것 같다!.

---