BOJ 13904 과제

BOJ 13904 과제

문제링크 : https://www.acmicpc.net/problem/13904

요약

정수 N과 N개의 과제 마감일까지 d(남은 일수)와 w(과제점수)를 입력받는다. 과제는 하루에 한개만 할수있을때 받을수 있는 가장 많은 점수를 출력하는 문제이다.

풀이

일다 점수를 최대한 많이 받으려면 기간내에 가장 많은 과제를 수행해야 하고 기간이 겹친다면 큰 점수를 선택하여야 한다. pair로 d와 w를 입력받고 남은 기간순으로 일단 정렬을 해준다.

정렬한 순서대로 일수를 카운트해주면서 점수를 더해주다가 일수가 중복되는 부분을 만나면 이떄까지 받았던 점수들중 가장 적은 점수를 제외해주고 세점수를 더해주면 된다. 최소힙을 이용해서 이떄까지 받았던 점수를 저장해준담에 top값을 pop해주는 식으로 구현 하였다.

코드

#include<iostream>
#include<vector>
#include<queue>;
#include<algorithm>
using namespace std;
vector<pair<int,int>>q;
priority_queue<int>pq;
int n,d,w;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d >> w;
		q.push_back({ d,w });
	}
	sort(q.begin(), q.end());
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < q.size(); i++) {
		cnt++;
		if (q[i].first >= cnt) {
			pq.push(-q[i].second);
			ans += q[i].second;
		}
		else {
			ans += pq.top();
			pq.pop();
			pq.push(-q[i].second);
			ans += q[i].second;	
			cnt--;
		}
	}
	cout << ans << "\n";
}