문제

문제 링크

해설

배경

• N일 내로 최대로 돈을 벌기 위해서는 n일에 선택할 수 있는 강의 중 최대한 이득이 되는 강의를 선택해야 합니다.
  • 1일차에 선택할 수 있는 강의들 중 가장 보수가 쌘 것을 일단 선택합니다.
  • 2일차에 선택할 수 있는 강의들 중 가장 보수가 쌘 것을 선택합니다.
    • 이때, 선택할 수 있는 강의 개수를 넘었다면, 1일차에 선택한 강의와 2일차에 선택한 강의 중 더 보수가 쌘 것을 고르면 됩니다.
• 위와 같은 과정을 n일차 까지 반복하면, 최적해를 구할 수 있습니다.
  • 이 과정에 가장 최적화된 자료구조는 바로 '우선순위 큐'입니다.
  • 삽입 시 루트노드가 최대/최소값임을 보장해주는 우선순위 큐는 n일차에 선택한 강의 중 한 개를 제거할 때 O(1)에 제거할 수 있게 해줍니다.

상세한 해설

1. 강연날짜(d)에 대해 오름차순(sort())으로 정렬합니다.
2. pair<> 자료형은 자동으로 first, second 순으로 정렬합니다. 즉, 먼저 first 순으로 오름차순 정렬이되고, 강연날짜(d)가 같다면 보수(p) 순으로 오름차순 정렬됩니다.
3. 위 배열에 대해 for()문을 보수를 우선순위 큐에 삽입합니다.
   • 이때, 우선순위 큐는 min heap으로 만듭니다.
   • priority_queue<int, vector<int>, greater<>>를 이용하면 C++17 기준으로 가장 값이 낮은 우선순위가 루트노드에 위치하는 min heap이 위치합니다.
   • Min heap으로 만든 이유는, 선택했을 때 가장 덜 이득이 되는 강의를 pop() 함수로 O(1)에 제거하기 위해서입니다.
4. d일에 고를 수 있는 강의의 개수는 d개입니다.
   • 따라서, if (pq.size() > i.first)라는 조건문을 사용해서, 우선순위 큐의 요소 개수가 d값을 넘어갈 때, 가장 덜 이득이 되는 루트노드를 pop()합니다.
5. 남아있는 우선순위 큐의 요소를 합산해서 정답을 출력합니다.

추가 내용

• 앞으로 전개되는 chapter 5의 그리디는 위와 같이 sort() 정렬과 priority_queue<> 우선순위 큐 또는 stack<> 과 같은 자료구조를 사용해서 조건에 맞는 최적해를 찾는 과정으로 해결합니다.
• 그러므로 이번 문제의 해결과정을 다시 한 번 눈여겨서 확인할 수 있도록 합시다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;
	
	vector<pair<int, int>> vec(N);	// d(기한), p(돈)
	for (int i = 0; i < N; ++i) cin >> vec[i].second >> vec[i].first;
	
	sort(begin(vec), end(vec));
	
	priority_queue<int, vector<int>, greater<>> pq;		// min heap
	for (const auto& i : vec) {
		pq.push(i.second);
		if (pq.size() > i.first) pq.pop();
	}
	int answer = 0;
	while (!pq.empty()) answer += pq.top(), pq.pop();
	cout << answer;
}

소스코드 링크

결과