백준 2023번 신기한 소수 :: 마이구미

이 글은 백준 알고리즘 2023번 문제 "신기한 소수" 를 풀이한다.

백트래킹을 통한 문제 풀이가 된다.

백트래킹에 대한 기본적인 이해가 필요하다면, 다음 글을 참고바란다.

http://mygumi.tistory.com/191

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

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

문제에서 정확히 이해해야하는 것은 왼쪽부터 N자리이다.

7331이 주어졌을 경우, 판단해야할 수는 다음과 같다.

7 => 1자리, 7은 소수
73 => 2자리, 73은 소수
733 => 3자리, 733은 소수
7331 => 4자리, 7331은 소수

1~4자리 모두 소수이기 때문에 7331은 신기한 소수라고 할 수 있다.

DFS 탐색을 1자리부터 ~ N자리까지 매번 소수를 판별하면서 탐색하면 쉽게 문제를 해결할 수 있다.

static int n;
static StringBuilder sb = new StringBuilder();
 
private void solve() {
    n = sc.nextInt();
 
    dfs("", 0);
    System.out.println(sb.toString());
}
 
public static void dfs(String s, int len) {
    if (n == len) {
        sb.append(s + "\n");
    } else {
        for (int i = 1; i <= 9; i++) {
            if (isPrime(Integer.parseInt(s + i))) {
                dfs(s + i, len + 1);
            }
        }
    }
    //backtracking
}
 
public static boolean isPrime(int k) {
    if (k == 1) {
        return false;
    }
 
    int sqrt = (int) Math.sqrt(k);
    for (int i = 2; i <= sqrt; i++) {
        if (k % i == 0) {
            return false;
        }
    }
    return true;
}