문제

문제 링크

해설

• 소의 도착시간과 검사시간을 하나의 선으로 나타내면 위와 같습니다.
• 먼저 소의 도착시간에 따라 오름차순으로 정렬하면 위 그림의 아래와 같습니다.
• 오름차순으로 정렬한 이유는 '라인스위핑 알고리즘'을 적용하기 위해서입니다.
  • 라인스위핑은 그리디 알고리즘과 마찬가지로 최적해를 구하기 위해 사용하는 알고리즘인데, 정렬된 요소를 시작점을 기준으로 끝까지 순차탐색하며 특정 판단조건을 적용해 최적해를 구하는 알고리즘을 말합니다.
  • 다른 알고리즘과 비교해 상대적으로 정의가 추상적인 편인데, 그만큼 알게모르게 사용하기 때문입니다.
• 모든 소를 검사해야 하기 때문에 빠르게 오는 순서대로 검사하는 것이 가장 빨리 검사를 끝낼 수 있다고 예상할 수 있습니다.
• 도착시간과 검사시간에 따라
  • 겹칠 경우, 먼저 온 소의 검사시간만큼 기다리고,
  • 겹치지 않을 경우, 이번 소의 도착시간 + 검사시간으로 갱신합니다.

코드

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;
	
	vector<pair<int, int>> vec(N);	// Arrive time, Examine time
	for (int i = 0; i < N; ++i) cin >> vec[i].first >> vec[i].second;
	
	sort(begin(vec), end(vec));
	
	int ans = 0;
	for (const auto& i : vec) {
		if (ans > i.first) ans += i.second;
		else ans = i.first + i.second;
	}
	cout << ans;
}

소스코드 링크

결과