[BaekJoon] 백준 2014번 소수의 곱

[BaekJoon] 백준 2014번 소수의 곱

 

 

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

 

 

내코드

 

- 조금 어려운 우선순위 큐 문제

- 알고리즘은 아래와 같다.

1. 주어진 소수를 배열에 저장

2. 주어진 소수를 priorityqueue에 넣는다.

3. priorityqueue에서 가장 작은 원소인 head를 꺼낸다.

4. 꺼낸 head와 주어진 소수들을 각각 곱한다.

5. 곱한 소수의 곱을 priorityqueue에 넣는다.

6. 단, 주어진 소수가 head의 약수인 경우 다음 iteration으로 바로 넘어간다.(중복 방지)

7. 3-6번 과정을 n-1번 반복한다.

8. priorityqueue에서 head를 꺼내고 출력한다.(n번째 꺼낸 head가 정답)

 

#include <string.h>
#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int k, n; cin >> k >> n;
	long long input[100];
	priority_queue< long long, vector<long long>, greater<long long> > pq;
	for (int i = 0; i < k; i++) {
		cin >> input[i];
		pq.push(input[i]);
	}
	for (int i = 0; i < n - 1; i++) {
		long long smallest = pq.top();
		pq.pop();

		for (int j = 0; j < k; j++) {
			pq.push(smallest* input[j]);
			if (smallest % input[j] == 0) break;
		}
	}
	long long result = pq.top();
	cout << result;
	return 0;
}

 

참고