[백준] 13904 - 과제

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

13904번: 과제

 

N개의 과제의 마감일과 점수가 주어졌을 때, 얻을 수 있는 과제 점수의 최댓값을 구하는 문제이다.

 

이 문제는 우선순위 큐를 이용하는 방법과 이용하지 않는 방법 두 가지로 풀 수 있다.

 

먼저 우선순위 큐를 이용하는 방법이다.

1. 입력으로부터 마감일이 가장 긴 날을 구한다.
2. 입력을 마감일 오름차순으로 정렬한다.
3. 1로부터 구한 최대 마감일부터 하루씩 줄여가며 우선순위 큐에 해당 날에 풀 수 있는 문제들을 모두 집어넣는다.
4. 매 날마다 우선순위 큐의 top을 답에 더해준다.

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

int n;
priority_queue<int> q;
pair<int, int> a[1001];

int main() {
	cin >> n;
	int day = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		day = max(day, a[i].first);
	}
	sort(a, a + n);
    
	int ans = 0;
	int idx = n - 1;
    
	for (int i = day; i >= 1; i--) {
    
		while (a[idx].first == i) {
			q.push(a[idx].second);
			idx--;
		}
        
		if (!q.empty()) {
			ans += q.top();
			q.pop();
		}
	}
	cout << ans;
}

 

다음은 단순 정렬로 구하는 방법인데, 우선순위 큐와 아이디어 자체는 크게 다르지 않다.

1. 입력을 점수 내림차순, 마감일 오름차순으로 정렬한다. 한마디로 점수가 큰 순으로, 같으면 마감일이 짧은 순으로 정렬한다.
2. 가능한 최대일에 해당 문제를 푼다.
   
   1. 문제를 점수가 큰 순으로 정렬했기 때문에, 그리디한 접근법이 가능하다.

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

bool compare(pair<int, int>& p1, pair<int, int>& p2) {
	if (p1.second == p2.second) {
		return p1.first < p2.first;
	}
	return p1.second > p2.second;
}

vector<pair<int, int>> v;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		v.push_back({ a,b });
	}

	int ans[1001] = { 0, };
	sort(v.begin(), v.end(), compare);
    
	for (int i = 0; i < n; i++) {
		int idx = v[i].first;
		while (idx > 0 && ans[idx]) {
			idx--;
		}
		if (idx > 0)ans[idx] = v[i].second;
	}
    
	int answer = 0;
	for (int i = 0; i <= 1000; i++)answer += ans[i];
	cout << answer;
}