백준 BOJ 13904 - 과제

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

13904번: 과제

지문부터 풀이과정까지 찔리는 문제...

 

과제를 가장 효율적으로 해결하려면

과제를 마지막날에 몰아서 하는게 가장 좋다.

몸으로경함하고있다.

 

그런데, 같은 날짜에 진행하려고 "다투는" 여러 과제의 경우에는,

가장 많은 점수를 받는 과제를 해결하는것이 당연히 효율이 좋다.

그래서 점수순으로 정렬해주고

해당 점수를 받을 과제를 처리할 날짜를 최대한 미뤄주면 정답이 된다.

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> v;
int score[1234] = {0};

int main(){
	int n,a,b;
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		v.push_back({-b,a});
	}
	
	sort(v.begin(), v.end());
	
	for(auto k : v){
		for(int j=k.second; j>=1; j--){
			if(score[j] == 0){
				score[j] = -k.first;
				break;
			}
		}
	}
	
	int ans = 0;
	for(int i=0; i<1234; i++){
		ans += score[i];
		/*if(score[i] != 0){
			printf("%d : %d\n", i, score[i]);
		}*/
	}
	cout << ans;
	return 0;
}

정렬할때 보면 {-b,a} 로 쌍을 넣어뒀는데,

기본 sort 함수는 가장 작은값부터 정렬해주기 때문에

모든 값에 음수를 한번 씌우고 계산할때 풀어주면

가장 큰 순으로 정렬하는걸 간편히 날먹할수있다.

 

실로 무난하게 풀었던 문제.