[백준] No.2014 - 소수의 곱 (C++)

문제

 

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

2014번: 소수의 곱

 

풀이

 

solved.ac 난이도: Gold 2

 

K개의 소수가 주어질 때 소수들의 곱으로 만들 수 있는 수들 중에서 N번째 수를 구하는 문제.

 

소수로 새로운 수를 만들 때마다 오름 차순 정렬하여 N번째 수를 찾아내기는 힘들다.

따라서 간단한 시간 복잡도를 가지는, 우선순위 큐를 활용하자.

최소 힙으로 구성된 우선 순위 큐는 루트(top)에 항상 가장 작은 수가 존재한다.

 

일단 간단히 브루트 포스로 풀고 최적화해보자.

 

입력받은 소수들을 모두 min_pq(최소 힙)에 넣고

 

min_pq의 top에 소수들을 곱해주어 새로운 수를 만들자.

만들어낸 수 들은 모두 min_pq에 넣어주자.

그 후, 사용한 top은 pop 해주고 count를 1 증가시킨다.

 

이를 count가 N이 될 때까지 반복해주면 된다.

단, 중복된 수가 큐에 삽입될 수도 있으므로 동일한 수는 제거해주자.

 

#include<queue>
#include<iostream>
using namespace std;
 
int main(){
  int prime_num, order;
  long long primes[100];
  priority_queue<int, vector<int>, greater<int>> min_pq;
  cin>>prime_num>>order;
 
  for(int i=0; i<prime_num ; ++i){
    cin>>primes[i];
    min_pq.push(primes[i]);
  }
 
  int count =0 ;
  long long prev_num=0;
  long long result;
 
  while(count != order){
    while(prev_num == min_pq.top()){//동일 수 제거
      min_pq.pop();
    }
    for(int i=0; i<prime_num ; ++i){
      result = primes[i] * min_pq.top();
      if(result >= INT32_MAX)//범위 초과는 저장X
        break;
      min_pq.push(result);
    }
    prev_num = min_pq.top();
    min_pq.pop();
    ++count;
  }
 
  cout<<prev_num<<'\n';
 
  return 0;
}

 

이러한 풀이도 시간 안에 통과 가능하지만 중복된 수의 연산과 동일한 수를 큐에 삽입하기 위한 메모리 낭비가 있다.

따라서 이번엔 중복된 수는 미리 차단하여 큐에 삽입하지 않는 풀이를 살펴보자.

해당 풀이는 슥지니 님의 게시글을 참조하였습니다.

[백준 2014번] 소수의 곱 - 슥지니의 코딩노트

 

중복된 수를 생성하지 않기 위한 규칙은 아래와 같다.

규칙: 수 생성 시, 항상 마지막에 곱해진 소수보다 같거나 작은 소수만을 곱한다.

 

즉, min_pq의 top에 곱하는 소수는 top이 생성될 때 마지막으로 곱해준 수보다 작거나 같아야 한다.

이러한 규칙을 강제하기 위해 min_pq.top( )을 head, 소수들을 primes[ ]라고 할 때

if(head % primes[i] ==0)인 경우 for문을 break 해준다.

 

 while(count != order){
    for(int i=0; i<prime_num ; ++i){
      head = min_pq.top();
      result = primes[i] * min_pq.top();
      
      if(result >= INT32_MAX)
        break;
 
      min_pq.push(result);
 
      if(head % primes[i] ==0)
        break;
    }
    min_pq.pop();
    ++count;
  }
 

문제의 예제로 생각해보자.

주어진 소수 2, 5, 7을 서로 곱하여 만들어지는 수는 아래와 같다.

2 x 2, 2 x 5, 2 x 7

5 x 2, 5 x 5, 5 x 7

7 x 2, 7 x 5, 7 x 7

 

빨간 수들과 파란 수들은 서로 곱해진 순서만 다르지만 결과는 같다.

이러한 수를 마지막으로 곱해진 소수보다 같거나 큰 수들만 곱하는 경우를 뽑으면

2 x 2,

5 x 2, 5 x 5,

7 x 2, 7 x 5, 7 x 7

 

중복된 수들이 사라진다.

head % primes[i] ==0를 break의 조건으로 거는 이유는

현재의 min_pq의 top인 head가 현재의 소수 primes[i]로 나누어진다면 head에는 primes[i]가 포함되어 있다는 의미이고

primes[i]보다 더 큰 이후의 소수들을 head에 곱해주는 것은 규칙에 어긋나 중복된 수를 발생시킨다.

 

이러한 조건을 통해

18과 같은 수가 생성될 수 있는 3가지 경우 중에서 오직 1번 만의 순서를 강제할 수 있다.

1. 3 x 3 x 2

2. 3 x 2 x 3

3. 2 x 3 x 3

 

 

 

문제의 해결 시간을 보면 실제로 중복이 있는 풀이보다 중복을 제거한 풀이가 메모리 면이나 시간 면에서 더 빠르다.

 

 

 

코드