[백준 14469] 소가 길을 건너간 이유 3

문제 링크 : https://www.acmicpc.net/problem/14469

14469번: 소가 길을 건너간 이유 3

먼저 소들이 검문소에 오는 순서대로 정렬해준다.

 

algorithm 헤더에 있는 sort 함수를 사용했는데

 

sort 함수로 구조체를 정렬하는 방법은 아래 글에 설명되어 있다.

 

https://tunafish78.tistory.com/81?category=880339

[STL] algorithm sort 함수 사용법

---

소들이 오는 순서대로 검문을 진행한다.

 

n번째 소가 검문을 하러 왔을 때

 

두가지 상황일 발생할 수 있다.

 

1. n-1번째 도착한 소가 검문을 받고 있는 경우

 

2. n-1 번째 도착한 소가 검문이 끝나서 들어갔을 경우

 

결국 n번째 소까지 검문하는 걸리는 시간은

 

상황에 따라

 

1. n-1번째 소가 끝나는 시간 + n번째 소가 검문하는데 걸리는 시간

 

2. n번째 소가 도착한 시간 + n번째 소가 검문하는데 걸리는 시간

 

이다.

 

n번째 소까지 검문하는데 걸리는 시간을 구했으므로

 

n+1, n+2, n+3 ... 

 

마지막 소까지 검문을 했을 때 끝나는 시간을 알 수 있다.

 

---

#include <iostream>
#include <algorithm>
#define n_ 105
using namespace std;

int n;
struct node {
	int x, y;

	bool operator<(node a) {
		return x < a.x;
	}
};
node arr[n_];
int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &arr[i].x, &arr[i].y);
	}
	sort(arr, arr + n);

	int res = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i].x > res) {
			res = arr[i].x + arr[i].y;
		}
		else {
			res += arr[i].y;
		}
	}
	cout << res << endl;
}