백준 2014번 소수의 곱

문제 링크입니다: https://www.acmicpc.net/problem/2014

흥미로운 우선순위 큐 문제였습니다.

알고리즘은 아래와 같습니다.

1. 숫자를 중복 삽입하는 것을 방지하기 위해 map을 이용합니다.

2. 소수의 곱을 우선순위 큐에 입력하는데 우선순위 큐의 크기가 N을 초과하고 우선순위 큐 내 최댓값보다 현재 숫자가 더 크면 삽입하지 않습니다.

-> 우선순위 큐 내 최댓값보다 현재 숫자가 작으면 현재 숫자가 더 먼저 등장하므로 우선순위 큐에 넣습니다.

3. 반복문을 탈출한 뒤 우선순위 큐의 top을 출력합니다.

#include <iostream>

#include <queue>

#include <vector>

#include <map>

#include <algorithm>

#include <functional>

using namespace std;

 

const int MAX = 100;

 

long long arr[MAX];

map<long long, bool> visited;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int K, N;

        cin >> K >> N;

 

        priority_queue<long long, vector<long long>, greater<long long>> pq; //minHeap

        for (int i = 0; i < K; i++)

                 cin >> arr[i];

 

        pq.push(1);

        long long maxValue = 0;

        while (N)

        {

                 long long cur = pq.top();

                 pq.pop();

 

                 for (int i = 0; i < K; i++)

                 {

                         long long next = cur * arr[i];

                         //pq 안에 있는 숫자들 중 최댓값보다 크고 pq의 크기가 N을 넘으면 더 이상 숫자를 넣을 필요가 없다

                         if (pq.size() > N && next > maxValue)

                                 continue;

                        

                         //중복 삽입 방지

                         if (!visited.count(next))

                         {

                                 maxValue = max(maxValue, next);

                                 visited[next] = true;

                                 pq.push(next);

                         }

                 }

                 N--;

        }

 

        cout << pq.top() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~