🙇‍♀️최대 수입 스케쥴(priority_queue 응용문제)

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

각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.

단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

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

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

▣ 입력예제 1 
6
50 2
20 1
40 2
60 3
30 3
30 1

▣ 출력예제 1
150

🚀풀이

먼저 가장 수입이 큰 거는 무조건 들어가야한다.

스케쥴을 체크를 하는데 만약 수입과 딸려온 일수에 이미 체크가 되어있다면 그 일수부터 차례로 내려와서 체크가 안된 일수에 체크를 한다.

그리고 그 돈값은 결과값에 더한다.

만약 모든 일수에 체크가 되어있다면 pop을 한다.

우선순위 큐가 빌 때까지 반복한다.

int n, m, d, res = 0, ch[10001];
priority_queue<pair<int, int>> pq;
void solve()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> m >> d;
		pq.push({ m, d });
	}

	while (true)
	{
		if (pq.empty())
			break;

		pair<int, int> t = pq.top();

		if (ch[t.second])
		{
			bool flag = false;
			for (int i = t.second; i >= 1; --i)
			{
				if (ch[i] == 0)
				{
					ch[i] = 1;
					res += t.first;
					pq.pop();
					flag = true;
					break;
				}
			}

			if (flag == false)
				pq.pop();
		}
		else
		{
			ch[t.second] = 1;
			res += t.first;
			pq.pop();
		}
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m, d, res = 0, ch[10001];
priority_queue<pair<int, int>> pq;
void solve()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> m >> d;
		pq.push({ m, d });
	}

	while (true)
	{
		if (pq.empty())
			break;

		pair<int, int> t = pq.top();

		if (ch[t.second])
		{
			bool flag = false;
			for (int i = t.second; i >= 1; --i)
			{
				if (ch[i] == 0)
				{
					ch[i] = 1;
					res += t.first;
					pq.pop();
					flag = true;
					break;
				}
			}

			if (flag == false)
				pq.pop();
		}
		else
		{
			ch[t.second] = 1;
			res += t.first;
			pq.pop();
		}
	}

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고