[C++] 최대 수입 스케쥴(priority_queue 응용문제)

📄문제

현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다.

각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

 

⬇️ 입력

첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

6 50 2 20 1 40 2 60 3 30 3 30 1

 

⬆️ 출력

첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

150

 

📝 풀이

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct lecture {
	int day;
	int cost;

	lecture(int cost, int day) : day(day), cost(cost) {}

	// 연산자 오버로딩으로 day를 내림차순 정렬할 수 있도록 설정
	bool operator < (const lecture& ref) const
	{
		return day > ref.day;
	}
};

int main()
{
	int N;
	scanf_s("%d", &N);

	vector<lecture> l;
	priority_queue<int> pQ;

	int day, cost, maxDay = INT_MIN, sum = 0;
	for (int i = 0; i < N; ++i)
	{
		scanf_s("%d %d", &cost, &day);
		l.push_back(lecture(cost, day));

		if (maxDay < day)
			maxDay = day;
	}

	// day를 기준으로 내림차순 정렬
	// day가 높아야 일을 늦게까지 대기시킬 수 있음
	sort(l.begin(), l.end());

	int j = 0;
	// day가 높은 순서대로 시작
	for (int i = maxDay; i >= 1; --i)
	{
		// 정렬된 l을 0부터 검사
		for (; j < N; ++j)
		{
			// 현재 선택된 day와 같다면 큐에 삽입
			if (l[j].day == i)
				pQ.push(l[j].cost);
			else
				break;
		}

		// 큐에 값이 있다면 pop하여 sum에 더하기
		if (!pQ.empty())
		{
			sum += pQ.top();
			pQ.pop();
		}
	}

	printf("%d", sum);
}

• 별도의 구조체를 통해 day를 기준으로 정렬이 가능하도록 연산자 오버로딩을 사용합니다.
• sort를 통해 day가 높은 순서대로 정렬합니다.
• 우선순위 큐에 각 day에 맞는 값을 모두 삽입하고, 큐가 비어있지 않다면 날마다 하나씩 꺼내 cost를 더합니다.