[BOJ 2023] 신기한 소수

문제링크#

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

문제 분석#

n 이 주어졌을 때, n 자리 수 중 문제에서 정의한 ‘신기한 소수’ 를 오름차순으로 출력한다.

전략#

가능한 범위 계산#

n 의 범위가 $1 ≤ N ≤ 8$ 로 정의되어 있기 때문에, 모든 경우의 수를 탐색하는 최악의 경우 순열을 만드는 경우의 수 * 앞부분 부터 소수인지 판단하는 경우의 수로 $(9 *8* 7 *6* 5 *4* 3 *2)* (8) * Primality Test)$ 의 시간이 걸린다.

소수 판단 전략 설계#

소수를 판단하기 위해서는 다음과 같은 방법이 있다.

에라토스테네스의 체 - 시간복잡도 $O(n \log(\log n))$ , 공간 복잡도 $O(n)$
나눠보는 방법 - 최적화했을 때 시간복잡도 $O(\sqrt{N})$
수의 범위가 정해져있기 때문에 처음에는 ‘에라토스테네스의 체’ 방법으로 구하려고 했으나, 메모리 제한에 걸려버렸다.

에라토스테네스의 체 방법을 사용했을 때, 메모리 소비량을 구해보자.

이 알고리즘에 의해 최악의 경우 ${100,000,000}$ 의 원소의 배열이 생기고 Java의 boolean 자료형을 사용하게 되면 배열의 총 크기는

${100,000,000} \text{ elements} \times 1 \text{ byte per element} = {100,000,000} \text{ bytes}$

이다.

이를 MB 로 환산하면

${100,000,000} \text{ bytes} \div {1,000,000} \text{ bytes per MB} = {100} \text{ MB}$

이므로 ${100} \text{ MB}$ 를 차지하게 된다!

따라서 문제의 메모리 제한을 넘어서게 되는 것이다.

따라서 에라토스테네스의 체가 아니라, 나눠보는 방법을 사용하여 소수를 판단해야 한다.

백트래킹 범위 줄이기#

나눠보는 방법을 사용하는 경우, 매번 현재 숫자의 자릿수 기준으로 수를 확인해야 하기 때문에 조금 더 최적화가 필요하다. 따라서 탐색 범위 자체를 줄여야 한다.

이를 위해 ‘신기한 소수’의 조건을 생각해보면 다음과 같다.

즉, 왼쪽부터 1자리, 2자리, 3자리, … n자리 수 모두 소수 여야 한다.

이 말은 어떤 수의 첫번 째 자리수부터 소수여야 한다는 뜻이다.

따라서 첫번째 수로 올 수 있는 숫자는 2, 3, 5, 7 으로 한정되며,

2 를 제외한 숫자는 소수가 될 수 없기 때문에 백트래킹을 이용해 숫자를 추가할 때도 홀수에 한해서만 추가할 수 있다.

시간 복잡도#

지금까지 설계된 내용을 통해 시간복잡도를 분석해보면 다음과 같다.

첫 번째 자리에 올 수 있는 수
{2, 3, 5, 7} 로 한정되므로 4 개의 경우만 고려한다.
백트래킹 탐색
각 자릿수마다 홀수 (1, 3, 5, 7, 9) 만 추가해서 탐색하기 때문에, 첫 번째 자릿수를 제외한 n - 1 개의 자릿수에 대해 5 가지 선택지가 존재한다.
따라서 $5 ^ {(n - 1)}$ 의 경우가 발생한다.
소수 판별
숫자 x에 대해 $\sqrt{x}$ 만큼의 연산이 필요하다.
최악의 경우 n 의 자릿수는 최대 $10^{n}$ 이므로 $\sqrt{10^n}$ 의 경우가 발생한다.

이 경우 대략 40억 정도의 경우가 만들어지지만,

백트래킹 알고리즘 내부에서 많은 경우의 수가 가지치기 된다.

다음과 같이 생각해보자.

두 번째 자리 수 까지 진행할 수 있는 수

→ 2자리 소수 중 첫째 자리 수가 1, 2, 3, 5, 7 인 수

→ 11, 13, 16, … 79 → 13개의 숫자만이 가능하고

세 번째 자리 수 까지 진행할 수 있는 수를 생각해보면 첫째 자리에서도 두번째 자리수에서도 조건을 만족하며 동시에 세 번째 자리 수에서 까지 조건을 만족해야 하기 때문에 진행할 수록 더 많은 수들이 가지치기 된다!

따라서, 이 문제는 백트래킹에서 어떻게 가지치기를 할 지 고민하는 것이 핵심 인 문제이다.

코드#


import java.util.*;
import java.io.*;

public class Main {

 static FastReader scan = new FastReader();
 static StringBuilder sb = new StringBuilder();

 static int n;
 static int[] first = new int[] {2, 3, 5, 7};

 public static void main(String[] args) {
  n = scan.nextInt();

  // 제일 첫번째 숫자부터 소수여야 하므로
  for (int i = 0; i < 4; i++) {
   solve(first[i], 1);
  }

  System.out.println(sb);
 }

 // 첫째 자리가 first 인 소수
 // idx 번째 수를 채운다.
 static void solve(int number, int idx) {
  if (idx == n) {
   sb.append(number).append('\n');
   return;
  }

  // 소수를 만족시키기 위해서, 일의 자리수는 1, 3, 5, 7, 9만 가능
  for (int val = 1; val < 10; val += 2) {
   int next = number * 10 + val;
   if (isPrime(next)) {
    solve(next, idx + 1);
   }
  }
 }

 static boolean isPrime(int number) {
  if (number < 2) {
   return false;
  }

  for (int i = 2; i * i <= number; i++) {
   if (number % i == 0) {
    return false;
   }
  }

  return true;
 }


 static class FastReader {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st;

  int nextInt() {
   return Integer.parseInt(next());
  }

  String next() {
   try {
    while (st == null || !st.hasMoreTokens()) {
     st = new StringTokenizer(br.readLine());
    }
   } catch (IOException e) {
    e.printStackTrace();
   }

   return st.nextToken();
  }
 }
}

느낀점#

재귀를 쓰기 때문에 메모리를 이미 많이 사용하는데, 동시에 에라토스테네스의 체까지 이용하게 되면서 메모리가 초과되었다.
백트래킹류의 문제를 풀 때, 시간이나 메모리가 초과될 때는 탐색 범위의 수를 줄일 수 있는 방법을 고민하는 것이 중요하다는 것을 배울 수 있었다.