[백준 20126] 교수님의 기말고사 (C++)

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

20126번: 교수님의 기말고사

문제

---

안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호에서 말고 다른 강의실에서 시험을 치를 수 없게 되었다.

공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 무조건 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학과 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

각 시험은 x_i분에 시작해서 y_i분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, x_i + y_i ≤ x_j 일 때 i 시험과 j 시험은 서로 겹치지 않는다.

안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

입력

---

다음과 같이 입력이 주어진다.

N M S
x1 y1
. . .
xN yN

 

출력

---

교수님이 시험을 시작할 수 있는 시각을 출력하여라. 시작 가능한 시각이 여러 개 있으면 그중 가장 앞선 시각을 출력한다. 시험을 치룰 수 없다면 -1을 출력하여라.

 

제한

---

• 1 ≤ N ≤ 100,000.
• 1 ≤ M ≤ S ≤ 1,000,000,000. 
• 0 ≤ x_i < x_i + y_i ≤ S.
• 입력에 주어진 수들은 전부 정수다.

 

문제 풀이

---

정렬을 이용한 문제.

시험을 시작 시간 기준으로 정렬한 후 현재 시간을 0으로 초기화한다. 그 후 i번째 시험 이전에 안 교수님의 시험을 치를 수 있는지 확인한다. 시험이 끝나는 시간인 현재 시간+M이 i번째 시험 시작 시간과 같거나 그 이전이라면 시험을 볼 수 있다. 아니라면 현재 시간을 i번째 시험이 끝나는 시간으로 둔다. 이를 끝까지 반복한다.

끝까지 반복하면 N-1번째 시험 이전까지 볼 수 있는지 아닌지 확인한 것이 되므로, 그 이후 시간부터 S까지 안 교수님의 시험을 치를 수 있는지 확인한다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M, S;
	int start, time;
	cin >> N >> M >> S;
	pair<int, int>* arr = new pair<int, int>[N];
	int current = 0;
	bool canTakeExam = false;
	for (int i = 0; i < N; i++)
	{
		cin >> start >> time;
		arr[i] = make_pair(start, time);
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		if (current + M <= arr[i].first)
		{
			canTakeExam = true;
			cout << current << "\n";
			break;
		}
		else
		{
			current = arr[i].first + arr[i].second;
		}
	}
	if (canTakeExam == false)
	{
		if (current + M <= S)
		{
			cout << current << "\n";
		}
		else
		{
			cout << "-1" << "\n";
		}
	}
	return 0;
}