[백준] 13904번 과제

13904번: 과제

점수를 최대한 많이 받아야 하기 때문에

점수를 기준으로 내림차순 한 후

score 배열을 만들어 마감일에 따라 받을 수 있는 점수를 저장한다.

 

W    D

60    4

50    2

40    4

30    3

20    1

10    4

5     6

 

내림차순 한 상태에서 첫 번째 인덱스부터 score 배열에 넣으면

score[4] = 60

'4일 안에 과제를 하면 60점을 얻는다'

라는 의미이다.

 

마찬가지로 두 번째 인덱스도 score 배열에 넣으면

score[2] = 50 이 된다.

 

세 번째 인덱스를 score 배열에 넣으려 하니

score[4]엔 이미 60이라는 값이 들어있다.

4일 안에 하는 과제는 이미 정해져 있는 것이므로

3일 안에 하는 과제로 바꿔본다.

score[3]은 아무 값도 저장되어 있지 않으므로

score[3] = 40 을 저장해준다.

 

네 번째 인덱스도 score 배열에 넣으려 하니

score[3]엔 이미 40이 저장되어 있다.

그러므로 2일 안에 하는 과제로 바꿔본다.

그러나 score[2]도 값이 저장되어 있는 상태이다.

그러므로 1일 안에 하는 과제로 바꿔본다.

score[1]에는 아무 값도 저장되어 있지 않으므로

score[1] = 30 을 저장해준다.

 

다섯 번째 인덱스는 score[1]엔 이미 30이라는 값이 있고

더 이상 일 수를 낮출 수 없기 때문에 그냥 넘어간다.

 

여섯 번째 인덱스도 score[4], score[3], score[2], score[1]

모두 값이 이미 있기 때문에 그냥 넘어간다.

 

마지막으로 일곱 번째 인덱스는

score[6] = 5

를 저장해준다.

 

그럼 최종적으로 score 배열은 이렇게 된다.

 

score[1] = 30

score[2] = 50

score[3] = 40

score[4] = 60

score[5] = 0

score[6] = 5

 

이 값들을 모두 더한 값이

얻을 수 있는 점수의 최댓값이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int main() {
	int N, d, w, Max = 0;
	cin >> N;
	vector<pair<int, int>> v;
	for (int i = 0; i < N; i++) {
		cin >> d >> w;
		v.push_back(make_pair(w, d));
		Max = max(Max, d);
	}
	sort(v.begin(), v.end(), greater<>());
	int score[1001] = { 0 };
	for (int i = 0; i < N; i++) {
		if (!score[v[i].second]) score[v[i].second] = v[i].first;
		else {
			for (int j = v[i].second - 1; j >= 1; j--) {
				if (!score[j]) {
					score[j] = v[i].first;
					break;
				}
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= Max; i++) res += score[i];
	cout << res;
	return 0;
}