[백준 14469] 소가 길을 건너간 이유3 (C++)

풀이

읽다 보니까 운영체제 프로세스 스케줄링이 생각나는 문제.

모든 소가 농장에 최소한의 시간으로 들어오려면 어떻게 해야 할까?

빨리 도착한 소부터 넣어주면 된다.

빨리 도착한 소부터 차례대로 하려면 도착시간을 기준으로 오름차순 정렬해주자.

 

처음 도착한 소는 도착 시간과 검문 시간을 모두 더해 정답에 넣어준다.

이유는 한 마리의 소만 존재한다면 그 소가 도착하고 들어간 시간이 정답이기 때문이다.

 

두 번째 소부터는 다음과 같은 규칙대로 시간을 계산한다.

이전에 들어온 소가 농장에 입장하기까지 걸린 시간을 ans라고 하자.

1. 두 번째 소가 ans보다 더 늦게 도착했다면, 즉 기다린 시간이 없다면

ans = 두 번째 소 도착 시간 + 검문 시간

2. 두 번째 소가 ans보다 빠르게 도착했거나 같다면 이 때는 기다린 시간이 존재한다.

따라서 ans = ans(이전 소의 입장 시간) + 두 번째 소의 검문 시간

 

이렇게 소를 하나씩 체크하면서 ans를 갱신해나가면 된다.

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

int n;
vector<pair<int, int>> v;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	v.reserve(n);
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end());
	int ans = v[0].first + v[0].second;
	for (int i = 1; i < v.size(); i++)
	{
		// 기다린 시간이 없으면 도착시간 + 검문시간
		if (ans <= v[i].first)
		{
			ans = v[i].first + v[i].second;
		}
		// 기다린 시간이 있다면 저장된 시간 + 검문시간
		else
		{
			ans = ans + v[i].second;
		}
	}

	cout << ans << '\n';
	return 0;
}