[백준 1263] 시간 관리 (C++)

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

1263번: 시간 관리

문제

---

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

입력

---

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 T_i와 S_i가 입력된다.

출력

---

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

제한

---

• 1 ≤ N ≤ 1,000
• 1 ≤ T_i ≤ 1,000
• 1 ≤ S_i ≤ 1,000,000

문제 풀이

---

정렬을 이용한 그리디 문제.

늦게 끝내도 되는 순서로 정렬한 후(=끝나는 시간 내림차순), 일을 끝마칠 수 있는 가장 늦은 시간 answer를 가장 늦게 끝내도 되는 일의 S-T로 초기화한다.

그리고 배열을 끝까지 탐색하면서 일을 끝마칠 수 있는 가장 늦은 시간을 조정한다. 만약 현재 answer가 현재 탐색 중인 인덱스의 일의 마감시간보다 작거나 같다면 해당 일을 포함했을 때 일을 끝마칠 수 있는 가장 늦은 시간은 해당 일에 걸리는 시간만큼 뺀 값이다.

마감 시간보다 크다면 현재 인덱스의 일의 S-T로 변경한다.

 

예시로 예제 입력 1을 들어보자.

4
3 5
8 14
5 20
1 16

 

늦게 끝내도 되는 순서로 정렬하면 answer는 15가 된다. 이는 이 일을 최대로 미뤘을 때 15시간까지 미룰 수 있음을 뜻한다. 

그 다음 탐색하는 일은 1 16이고, 이전 탐색된 일을 해야 하는 시간을 고려하면 answer 값인 15시간 안에는 마무리해야 한다. 따라서 이 일을 최대로 미뤘을 때 14시간까지 미룰 수 있다. 14시간째 ~ 15시간째에는 이 일을 진행해야 차질이 없다.

그 다음 탐색하는 일은 8 14이고, 이전 탐색된 일을 해야 하는 시간을 고려하면 answer 값인 14시간 안에는 마무리해야 한다. 따라서 6시간까지는 이 일을 미룰 수 있다. 6시간째 ~ 14시간째에는 이 일을 진행해야 차질이 없다.

그 다음 탐색하는 일은 3 5이고, 이전 탐색된 일을 해야하는 시간만 고려하면 6시간 안에 마무리해야 하지만, 이 일의 자체 마감 시간이 5시이고, 3시간 걸리므로 2시에는 이 일을 진행해야 한다.

 

아래는 코드.

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

bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
	if (p1.second > p2.second)
	{
		return true;
	}
	else if (p1.second == p2.second)
	{
		return p1.first < p2.first;
	}
	else
	{
		return false;
	}
}

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

	int N;
	cin >> N;
	pair<int, int>* arr = new pair<int, int>[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}
	sort(arr, arr + N, cmp);
	int answer = arr[0].second - arr[0].first;
	for (int i = 1; i < N; i++)
	{
		if (answer > arr[i].second)
		{
			answer = arr[i].second - arr[i].first;
		}
		else
		{
			answer -= arr[i].first;
		}
	}
	if (answer < 0)
	{
		answer = -1;
	}
	cout << answer<< "\n";
	return 0;
}