BOJ 13904 과제

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

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";
}