[BOJ] 백준 13904. 과제 (Gold III)

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

13904번: 과제

이 문제 역시 예전에 해결했던 문제이다.

그러나 복습 겸 다시 한 번 풀어보았다.

---

의식의 흐름 및 해설

역시 골드 난이도 답게 호락호락하지 않았다.

확실한 건 점수를 많이 얻을 수 있는 과제를 많이 할 수록 좋다는 점이다.

당연해보이지만, 여기까지 접근했다면 30%는 맞는 셈.

 

그런데 최대한 많은 과제를 하기 위해선 마감기한이 최대한 앞에 있는 것을 하는 게 좋지 않을까?

그렇다고 마감기한 순으로 정렬하면 더 높은 점수를 받을 수 있는 과제도 건너뛰어버린다.

이러한 점때문에 다소 어렵게 느껴진다.

 

dp로 할 수 있을까? dp로 하려면 dp[i][j]: i번째 과제를 할 경우 총 j만큼의 점수를 얻을 수 있다는 점화식을 세워보자.

그럼 dp[N][N*w] 라서 배열의 크기가 너무 크기도 하고, 시간초과가 나올 것이다.

따라서 dp는 범위나 시간제한을 봐서라도 아예 시도조차 하지 않게 될 것이다.

 

그럼 어떻게 하면 좋을까?

 

바로 마감일이 빠른 것부터 정렬하되,

마감일이 지나버린 과제가 등장했을 경우, 현재 한 과제 중에서 점수가 더 낮은 과제를 제외해버리는 방법을 사용하면 된다.

이런 코드에 제적격인 자료구조가 있다. 바로 우선순위 큐이다. (이 문제는 우선순위 큐를 사용하지 않아도 AC를 받을 수는 있지만, 난 우선순위 큐를 이용하였다.

 

() 연산자 오버로딩으로 priority_queue 정렬 조건을 세팅해준다.

이 때 정렬조건이 평범한 정렬조건의 반대임에 주의하자.

점수가 더 낮은 것이 top에 오도록 설정하여, 제외할 과제의 점수를 낮은 순부터 나올 수 있게 해주자.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M;
vector<pi> v;
bool cmp(pi p1, pi p2) {
	if (p1.first == p2.first)
		return p1.second > p2.second;
	return p1.first < p2.first;
}
struct cmp2 {
	bool operator()(pi p1, pi p2) {
		if (p1.second == p2.second)
			return p1.first > p2.first;
		return p1.second > p2.second;
	}
};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i].first >> v[i].second;
		M = max(M, v[i].first);
	}
	sort(all(v), cmp);
	priority_queue<pi, vector<pi>, cmp2> pq;
	int ans = 0, day = 1;
	for (int i = 0; i < N; i++) {
		while (!pq.empty() && v[i].first < day) {
			if (pq.top().second > v[i].second)
				break;
			ans -= pq.top().second;
			pq.pop();
			day--;
		}
		if (v[i].first >= day) {
			ans += v[i].second;
			pq.push(v[i]);
			day++;
		}
	}
	cout << ans << "\n";
}