[백준 13904번 / C++] 과제

​#접근방법

 

점수의 최댓값을 얻기 위해서는 당연히 과제 점수가 높은 것을 제일 먼저 할당 받아야한다. 

 

그렇기 때문에 처음에 입력받을 때 마감일 d와 점수 w 를 정렬해줘야한다. 

 

우선 제일 중요한 과제 점수가 높은 것부터 내림차순으로 정렬해주었다. 

그리고 만약 과제 점수가 같을 경우네는 마감일이 짧은것부터 오름차순으로 정렬했다. (실행해본결과 상관없는 조건이다)

 

아무튼 과제 점수가 높은 것들부터 해서 cost라는 배열에 집어넣어준다. 

 

예를 들어 , 마감일이 4이고 점수가 50이라면 

인덱스 4를 가지고 있는 cost라는 배열에 50을 저장한다. 

 

이후에 마감일 4이고 점수가 40이 들어왔을 경우 마감일 1~3 일을 차례대로 훑어보면서 빈자리에 넣어준다. 

만약 빈자리가 없다면, 이전에 더 높은 점수를 가지는 과제들이 해당 자리를 차지 했다고 생각하면 된다. 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std; 
int cost[1002]; 

bool cmp( pair<int, int>& v1, pair<int, int>& v2 ) {

	if (v1.second == v2.first) {
		return v1.first < v1.first; 
	}
	else return v1.second > v2.second; 
}

int main() {
	
	int  n; cin >> n;

	vector <pair<int, int>> v(n); 

	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second; 

	}
	sort(v.begin(), v.end(), cmp);

	int res = 0; 
	for (int i = 0; i < n; i++) {
		for (int j = v[i].first; j > 0; j--) {
			if (!cost[j]) {
				cost[j] = v[i].second; 
				res += v[i].second; 
				break; 
			}
		}
	}
	cout << res; 
}

13904번: 과제