[백준 C++] 1202번: 보석 도둑

1. 문제

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

1202번: 보석 도둑

 

2. 알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

3. 소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define MAX_N 300000
#define MAX_K 300000

using namespace std;

int N, K;
pair<int, int> gems[MAX_N];
int backpack[MAX_K];
priority_queue<int, vector<int>, less<int>> pq;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 보석의 갯수, K : 가방의 갯수
	cin >> N >> K;

	// 보석의 정보 입력
	for (int i = 0; i < N; i++)
		cin >> gems[i].first >> gems[i].second;

	// 가방의 최대 무게 입력
	for (int i = 0; i < K; i++) 
		cin >> backpack[i];

	// 보석과 가방 정보를 무게 오름차순 정렬
	sort(gems, gems + N);
	sort(backpack, backpack + K);

	int gem_idx = 0;
	long long sum = 0;

	// 최대 무게가 작은 가방부터 넣을 수 있는 보석 탐색
	for (int i = 0; i < K; i++) {
		while (gem_idx < N && backpack[i] >= gems[gem_idx].first) {
			pq.push(gems[gem_idx].second);	// 현재 가방에 넣을 수 있는 보석들을 Priority Queue에 Push
			gem_idx++;
		}

		if (!pq.empty()) {
			sum += pq.top();	// 현재 가방에 넣을 수 있는 보석 중에서 가격이 제일 비싼 보석 꺼내기
			pq.pop();
		}
	}

	cout << sum;

	return 0;
}

 

4. 유용한 문법 및 알고리즘

1) 정렬

// 오름차순 정렬
sort(backpack, backpack + K);

// 내림차순 정렬
sort(backpack, backpack + K, greater<int>());

 

2) 우선순위 큐 정렬

// 큰 수가 먼저 pop
priority_queue<int> pq;

// 작은 수가 먼저 pop
priority_queue<int, vector<int>, greater<int>> pq;