[백준/BOJ] 백준 13904번 : 과제

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

13904번: 과제

 

날짜별로, 해당 날짜가 마감인 날의 과제 점수들을 저장해 놓고, 마감일이 큰 해당 날짜부터 역순으로 확인해 나아가면서 해당 날짜가 마감일인 점수들을 우선순위 큐에 넣고 우선순위 큐에서 가장 큰 점수를 추출해서 해당 과제를 수행해 나아가는 방식으로 문제를 해결했다.

 

마감일이 큰 날짜부터 확인하므로, 이전에 확인한 마감일에서 우선순위 큐에 넣어둔 것들은 현재 마감일에도 해결할 수 있는 과제가 되는 것이다.

 

코드

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

int n;
vector<int> costs[1005]; //[날짜] = 그 날짜가 마감인 날의 점수들
priority_queue<int> pq; //가장 큰 점수가 먼저 나오는 우선순위 큐
int max_day = 0;

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int d, w;
		cin >> d >> w;

		costs[d].push_back(w);
		max_day = max(max_day, d);
	}

	for (int i = 0; i < 1005; i++) {
		sort(costs[i].begin(), costs[i].end()); //날짜별 점수 순서로 정렬
	}

	int result = 0;

	//마감일이 큰것부터 확인
	for (int i = max_day; i >= 1; i--) {

		//해당 날짜가 마감일인 점수를 pq에 넣는다
		//그러므로 이전에 pq에 담긴것도 해당 날짜에도 해결할 수 있는 과제
		for (int j = 0; j < costs[i].size(); j++) {
			pq.push(costs[i][j]);
		}

		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}

	cout << result;

	return 0;
}