<PQ> BOJ 2014 소수의 곱

문제

k개의 소수가 있습니다. 이 소수들 중에서 몇개를 곱해 얻게 되는 수들을 정렬하여 n번째 수를 구하는 문제 입니다. 얻게 되는 수에는 주어진 소수 자체도 포함시킵니다.

• 소수 개수 k <= 100
• n <= 100000

접근

먼저 몇개의 소수를 곱해 얻을 수 있는 수를 어떻게 구하면 좋을까요?

사실 중복 사용이 가능하기 때문에 얻을 수 있는 숫자는 무한개 입니다. 따라서 숫자를 모두 구하고 정렬해서 n번째 숫자를 알아내는건 불가능합니다. 결국 작은 수부터 순서대로 n번째 까지 구해야 하는데요.

이를 위해 그래프를 탐색(bfs, dfs)하듯이 탐색하며 n번째 수를 구해볼건데요. 이때 bfs의 큐 대신 우선 순위 큐를 사용해봅니다. 물론 bfs는 아닙니다. 우선순위에 따라 순서가 바뀌므로 최단 거리를 구하는 것이 아니기 때문입니다.

예를 들어 소수 2, 5, 7 세개가 주어지면 맨 처음 큐에는 2,5,7을 넣어주겠죠. 2가 가장 작으므로 맨 처음 나와서 2, 5, 7을 곱해 다시 큐에 넣어줄 겁니다. 그러면 큐에는 5, 7, 4, 10, 14가 들어있게 되고 우선 순위 큐이므로 4, 5, 7, 10, 14로 들어가 있을 겁니다. 다음 턴에서 4가 나오게 되겠죠. 여기서 주목할 점은 일반적인 큐라면 5가 나왔을 텐데 우선 순위 큐를 이용함으로써 더 작은 4가 먼저 나오게 되고 문제에서 구하라고 한 정렬하여 n번째 숫자를 구하는데 가까워 집니다.

그런데 이렇게 하다보면 중복 처리에 대한 문제가 생깁니다. 예를 들어 10같은 경우에는 2x5, 5x2 등으로 두번이나 등장하게 됩니다. 이런 중복은 어떻게 처리해주면 될까요?

1.check 배열

배열을 사용해주는건 말도 안됩니다. 최대 가능한 정답이 $2^{31}-1$까지 가능하기 때문에 이 모든 수를 배열에 넣어주면 21억x1byte= 21기가바이트는 말도 안됩니다.

2. 중복되는 숫자가 등장하면 모두 poll시키기

우선순위 큐를 이용해 방문하다보니 중복되는 숫자들은 연속으로 있게 됩니다.따라서 숫자를 poll시키고 뒤에 숫자가 같다면 큐에서 계속 제거해주는 방법을 사용할 수 있습니다. 그치만 이 방법을 사용하면 이 모든 중복되는 숫자가 결국 큐에 들어가기 때문에 이 역시 메모리가 초과됩니다.

3. 큐에 중복되는 수를 넣지 않는 방법

큐에 중복되는 수를 아예 넣지 않기 위해 언제 중복이 발생하나 생각해봅니다. 같은 숫자의 조합으로 곱하면 중복이 발생하겠죠? 같은 숫자의 조합을 피하려면 어떻게 하면 좋을까요?

예를 들어 우리가 이중 for문으로 주어진 숫자에서 숫자 두개를 고르는 방법을 모두 출력하려면 어떻게 할까요? 중복사용은 허용하구요. 고전적으로 아래와 같은 방법 많이들 사용하실거라 생각합니다. j=i을 사용해서 i보다 앞에 오는 수는 보지 않는거죠 왜냐하면 다른 조합에서 보게 될 테니까요. 총 6개가 나오는데요. $_3H_2$($_4C_2$)에 의해 맞는 결과네요.

int[] numbers = {1, 2, 3};

for(int i = 0; i<3; i++){
  for(int j = i; j<3; j++){
    System.out.println(numbers[i]+" "+numbers[j]);
  }
}

// 1 1
// 1 2
// 1 3
// 2 2
// 2 3
// 3 3

자 그럼 이걸 생각하고 소수의 곱으로 중복되는 수를 피하려면 어떻게 하면 될까요? 현재 수를 소인수분해해서 가장 큰 소인수보다 크거나 같은 소수만 사용하는 겁니다. 또 예를 들어보면 현재 수가 5라고 하면 가장 큰 소인수보다 크거나 같은 5, 7만 곱할 수 있습니다. 이렇게 되면 아까처럼 10이 중복되는 일이 없습니다. 숫자 n의 가장 큰 소인수를 구하는 코드는 아래와 같습니다.

static int getMaxPrimeFactor(int n){
  int returnValue = -1;
  
  for(int i = 2; i*i<=n; i++){
    while(n % i == 0){
      returnValue = i;
      n /= i;
    }
  }
  
  if(n != 1){
    return n;
  }
  
  return returnValue;
}

n != 1일때 그대로 n을 출력해버린건 우리가 n을 2부터 나눠봤기 때문이에요. 왜냐하면 1로만 나누어지는 소인수가 있었다면 그것이 가장 큰 소인수이고 for문을 통해 거르지 못했기 때문입니다. 이런 예로 $2^2 * 3 * 13$ 같은 경우가 있겠네요.

최종적으로 위의 방법들을 적용해서 n번째 수를 출력해주면 정답이 됩니다.

코드

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

class baek__2014 {

    static int factorization(int n) {
        int max = -1;

        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                max = i;
                n /= i;
            }
        }

        if (n != 1)
            max = n;

        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        int k = Integer.parseInt(temp[0]);
        int n = Integer.parseInt(temp[1]);

        int[] prime = new int[k];
        temp = br.readLine().split(" ");
        for (int i = 0; i < k; i++) {
            prime[i] = Integer.parseInt(temp[i]);
        }

        PriorityQueue<Integer> q = new PriorityQueue<>();

        q.add(1);
        int cnt = -1;
        int answer = -1;

        while (true) {
            int now = q.poll();
            cnt++;

            if (cnt == n) {
                answer = (int) now;
                break;
            }

            int max = factorization(now);

            for (int p : prime) {
                if (p < max)
                    continue;

                long nex = (long) now * p;

                if (nex < (long) (1 << 30) * 2)
                    q.add((int) nex);
            }
        }

        System.out.print(answer);

    }
}