백준 2109번 순회강연

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

2109번: 순회강연

 

문제의 핵심은 정확히 d일에 강연을 하는 것이 아니라 d일 안에 강연을 하는 것이었습니다.

 

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

1. 주어진 p와 d를 d를 기준으로 오름차순으로 정렬합니다.

2. 최소힙을 생성하고 정렬된 순서대로 p를 힙에 넣어줍니다.

2.1 단, 힙의 크기가 넣어준 p의 쌍인 d를 초과할 경우, 힙 내에서 가장 작은 p값인 pq.top()을 제거합니다.

3. 2번 과정을 마친 후, 힙 내의 모든 값들을 더한 값이 최대로 벌 수 있는 금액입니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <functional>
	using namespace std;
	const int MAX = 1e4;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	while (n--)
	{
	int p, d;
	cin >> p >> d;
	v.push_back({ d, p });
	}
	sort(v.begin(), v.end());
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < v.size(); i++)
	{
	pq.push(v[i].second);
	if (pq.size() > v[i].first)
	{
	pq.pop();
	}
	}
	int result = 0;
	while (!pq.empty())
	{
	result += pq.top();
	pq.pop();
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

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