[BOJ] 6068번 시간 관리하기 (C++)

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

6068번: 시간 관리하기

 

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

bool compare(pair<int, int>& a, pair<int, int>& b){
	if (a.second == b.second) return a.first > b.first;
	return a.second > b.second;
}

int main() {
	int n, t, s, time;
	vector<pair<int, int>> v;
	
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> t >> s;
		v.push_back({t, s});
	}
	
	sort(v.begin(), v.end(), compare);
	time = v[0].second - v[0].first;
	
	for(int i = 1; i < n; i++){
		if(time < v[i].second) time -= v[i].first;
		else {
			time = v[i].second;
			time -= v[i].first;
		}
	}

	if(time < 0) cout << -1 << endl;
	else cout << time << endl;
	
	return 0;
}

1263번과 비슷한데 어떤 일을 마칠 때까지 그 일만 해야한다는 조건이 추가된 문제이다.

 

 

끝내야할 시간(t)와 걸리는 시간(s)를 입력받아 벡터에 넣는다. 끝내야할 시간이 늦은 일이 먼저 오도록 정렬한다.

맨 처음 끝내야할 시간이 가장 늦은 일에서  t - s는 시작하는 시간(tmp)이다. 

 

일을 끝내야할 시간이 이전 일을 시작하는 시간(time)보다 늦다면 time에서 걸리는 시간만큼을 빼주고

일을 끝내야할 시간이 이전 일을 시작하는 시간(time)보다 빠르다면 일을 끝내야할 시간에서 걸리는 시간만큼을 빼준다.

 

time은 일을 최대한 늦게 시작하는 시간이 된다.

time이 0보다 작다면 0시부터 시작하여도 일을 끝마칠 수 없는 것이므로 -1을 출력하고

그렇지 않으면 time을 출력한다.