문제

풀이 과정

백트래킹을 요구하는 문제.
메모리 용량을 알고 있었지만 그래도 혹시나 하는 맘에 에라토스테네스의 체를 썼는데 안되었다.
방법이 뭐가 있을지 고민하다가, 테스트케이스를 보니, 약간의 공통점?이 있었다.

1. 일단 수의 맨 첫자리가 소수가 아니라면 그 수는 신기한 소수가 아니다. 즉 맨 첫자리는 2,3,5,7 이어야 한다.
2. 2~N 자리수까지 짝수가 있거나, 5가 있으면 안된다. 짝수는 2로 나누어지고 5는 5로 나뉘기 때문.

DFS() 를 활용하여, 한자리씩 숫자를 누적해간다. 백트래킹을 통해, 걸러주고 최종 N자리수 까지 도달한 수가 신기한 소수이다.

정답

import java.util.Scanner;

public class Main {
    static boolean[] prime = new boolean[10];
    static int N;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        prime[2] = prime[3] = prime[5] = prime[7] = true;
        DFS("", 0);
        System.out.println(sb.toString());
    }

    private static void DFS(String str, int cnt) {
        if (cnt == N) {
            sb.append(str).append("\n");
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (cnt == 0 && !prime[i]) continue;
            if (checkPrime(str + i)) DFS(str + i, cnt + 1);
        }
    }

    private static boolean checkPrime(String strNum) {
        int tempNum = Integer.parseInt(strNum);
        for (int i = 2; i <= Math.sqrt(tempNum); i++) {
            if (tempNum % i == 0) return false;
        }
        return true;
    }
}