[BOJ] 13904번 과제 (C++)

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

13904번: 과제

 

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

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	int arr[1001] = {0, };
	for(int i = 0; i < n; i++){
		int d, w;
		cin >> d >> w;
		v.push_back({w, d});
	}
	sort(v.begin(), v.end(), greater<>());
	int sum = 0;
	for(int i = 0; i < n; i++){
		for(int j = v[i].second; j >= 1; j--){
			if(arr[j] == 0){
				arr[j] = v[i].first;
				sum += v[i].first;
				break;
			}
		}
	}
	cout << sum << endl;
	return 0;
}

 

먼저, (과제 점수, 남은 일수)를 과제 점수가 높은 순으로 정렬하면 다음과 같다.

60 4

50 2

40 4

30 3

20 1

10 4

5 6

 

정렬된 순서대로 마감일에 최대한 가깝게 넣어준다.

첫 번째 과제는 4일에 하도록 설정한다.  arr[4] = 60

두 번째 과제는 2일에 하도록 설정한다.  arr[2] = 50

세 번째 과제는 이미 4일에 하기로 한 과제가 존재하므로, 마감일에 최대한 가깝게 3일에 하도록 설정한다.  arr[3] = 40

네 번째 과제는 이미 3일, 2일에 하기로 한 과제가 존재하므로, 마감일에 최대한 가깝게 1일에 하도록 설정한다.  arr[1] = 30

다섯 번째 과제와 여섯 번째 과제는 마감일 안에 할 수 없으므로 패스

마지막 과제는 6일에 하도록 설정한다.  arr[6] = 5

 

따라서 최대 점수는 60 + 50 + 40 + 30 + 5 = 185점이 된다.