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

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

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

 

(도착시간, 검문시간)을 pair 형태로 저장하고 도착시간 기준 오름차순 정렬한다.

도착시간+검문시간이 다음 소의 도착시간보다 작다면 현재소와 다음소 사이의 공백기간이 생기고,

도착시간+검문시간이 다음 소의 도착시간보다 크거나 같다면 다음 소는 그만큼 기다려야한다.

 

 

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

int main()
{
    int n;
    cin >> n;
    vector<pair<long long, long long>> v;
    v.resize(n);
    for(int i = 0; i < n; i++)
    {
        cin >> v[i].first >> v[i].second;
    }

    // 도착시간 기준 오름차순 정렬
    sort(v.begin(), v.end());

    long long time = v[0].first + v[0].second;
    for(int i = 1; i < n; i++)
    {
        if(time < v[i].first)
        {
            time = v[i].first + v[i].second;
        }
        else
        {
            time = time + v[i].second;
        }
    }

    cout << time;
}