< 백준 BaekJoon : 1026번 보물 > C++

<< 문제 >>

 

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

 

<< 풀이 >>

단순히 생각하면 A의 큰 값과 B의 작은 값을 곱해주면 작은 값이 됩니다.

 

B에 있는 수를 재배열하면 안된다고 조건이 있지만, 사실 이는 문제 풀이에서 크게 상관이 없습니다.

 

만약 B를 재배열하지 않도록 하려면 <B의 값, index>로 Map을 만들어서 사용하면 될 것 같네요.

 

<< 코드 >>

#include <queue>
#include <iostream>
using namespace std;
int main() {
	priority_queue<int> pqA;
	priority_queue<int> pqB;
	
	int n;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		int temp;
		cin >> temp;
		pqA.push(-temp);
	}
	for(int i=0; i<n; i++)
	{
		int temp;
		cin >> temp;
		pqB.push(temp);
	}
	
	int result = 0;
	for(int i=0; i<n; i++)
	{
		result -= pqA.top() * pqB.top();
		pqA.pop();
		pqB.pop();
	}
	
	cout << result;
}

  

A에서 -를 붙인 이유는 pq가 내림 차순으로 정렬되기 때문에 -를 붙인다면 오름차순으로 사용할 수 있기 때문입니다.

 

 

<< 깃헙 >> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1026.%E2%80%85%EB%B3%B4%EB%AC%BC

StudyAlgorithm_Part2/백준/Silver/1026. 보물 at main · J2on/StudyAlgorithm_Part2