[백준] 13904번 과제

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

13904번: 과제

가장 마지막날부터 첫째날까지 거꾸로 계산해야 한다는 것은 문제를 보자마자 느꼈다. 처음에는 동적 계획법으로 풀어야 하나? 싶었는데 생각보다 쉽게 풀 수 있었다.

예를 들어 입력이

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

이렇게 들어온다면

6일째에는 6 이상인 것이 5밖에 없으니 5

5일째에는 5 이상인 아직 하지 않은 과제가 없으므로 과제를 할 수 X

4일째에는 4 이상인 아직 하지 않은 과제들 중에서 최댓값인 60을 선택

3일째에는 3 이상인 아직 하지 않은 과제들 중에서 최댓값인 40을 선택

2일째에는 2 이상인 아직 하지 않은 과제들 중에서 최댓값인 50을 선택

1일째에는 1 이상이 아직 하지 않은 과제들 중에서 최댓값인 30을 선택

따라서 5 + 60 + 40 + 50 + 30 = 185가 되는 것이다.

이런 식으로 풀면 된다. 주의해야 할 것은 이미 한 과제의 점수는 벡터에서 삭제해야 한다는 것이다.

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

int n;
vector<int> v[1001];


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	int day, score;
	int maxDay = 0;
	for (int i = 0; i < n; i++) {
		cin >> day >> score;
		v[day].push_back(score);
		if (day > maxDay)
			maxDay = day;
	}
	int sum = 0;
	for (int i = 1; i <= maxDay; i++) {
		sort(v[i].begin(), v[i].end());
	}
	for (int i = maxDay; i >= 1; i--) {
		int maxScore = -1;
		int maxJ;
		for (int j = i; j <= maxDay; j++) {
			//erase 꼭 하기
			if (v[j].size() != 0) {
				if (v[j][v[j].size() - 1] > maxScore) {
					maxScore = v[j][v[j].size() - 1];
					maxJ = j;
				}
			}
		}
		if (maxScore != -1) {
			sum += maxScore;
			v[maxJ].erase(v[maxJ].begin() + v[maxJ].size() - 1);
		}

	}
	cout << sum;
	system("pause");
	return 0;
}