[2014번] 소수의 곱

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 힙

2. Priority Queue STL

3. MAP STL :: http://www.crocus.co.kr/604

이 문제는 해설을 보기전에 충분한 시간을 가지고 곰곰이 생각해보는 것이 좋다.

2,3,5,7이 있다고 보자.

처음에 arr배열에 값을 넣어줌과 동시에 최소 힙에도 값을 같이 넣어준다.

(arr :: 곱할 대상, 최소 힙 :: 곱해질 대상)

이 arr 배열을 작은 값이 먼저 나오도록 오름차순으로 정렬을 한 번 해주고

(물론 안해도 괜찮지만 힙에서 좀 더 시간을 아끼기 위해.)

최소 힙에서 값을 하나씩 꺼내며 그 값과 arr[]의 값을 for문을 통해 한번씩 곱해주고 

그 결과를 다시 최소 힙에 넣어준다.

이때 map STL을 이용하여 중복되는 값이 최소 힙에 또 들어가는지 확인하고 중복 되지 않는다면 그 값을 넣어준다.

            // k개를 넘어간 것에다가 현재 최대값보다 큰 값은 필요없다.

            if (q.size() + cnt > k && max < v)

                break;

이 코드의 의미는 주석과 같이 현재 k번째 값을 알고 싶은데 q.size() + cnt = 지금까지 카운트 해온 모든 값을 의미하고

q.size() + cnt > k && max < v라는 의미는 k번째를 넘어서는 값이기도 하며 v값이 최댓값을 넘긴다면

최소 힙에서 정답과 무관한 값이 계속들어가게 될 것을 방지하기 위해 저런 코드를 심어두었다.

저 코드가 없다면 메모리 초과를 받게 된다.

소스 코드 : 

#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
 
#define MAX(a,b) (a > b ? a : b)
#define ll long long
 
using namespace std;
 
ll arr[103];
 
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
 
    // 최소 힙으로 구현된 q
    priority_queue <ll, vector<ll>, greater<int>> q;
    map<ll, int> chk;
 
    for (int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
        q.push(arr[i]);
    }
 
    sort(arr, arr + n);
 
    ll max = 0;
    int cnt = 0;
 
    while (!q.empty())
    {
        ll front = q.top();
        q.pop();
 
        cnt++;
 
        if (cnt == k)
        {
            printf("%lld\n", front);
            break;
        }
 
        for (int i = 0; i < n; i++)
        {
            ll v = front * arr[i];
 
            // k개를 넘어간 것에다가 현재 최대값보다 큰 값은 필요없다.
            if (q.size() + cnt > k && max < v)
                break;
 
            // 중복체크(이미 큐에 존재하는 것은 넣지 않는다.)
            if (chk[v] == 0)
            {
                max = MAX(max, v);
 
                chk[v] = 1;
                q.push(v);
            }
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>