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

작성일 | In

문제 링크

  • http://icpc.me/14469

문제 출처

  • USACO 2017 February Contest Bronze 3번

풀이

먼저 들어온 것을 먼저 차리해야 하므로 도착 시간을 기준으로 정렬을 먼저 해줍시다.

도착 시간을 x[i], 검문 시간을 y[i], 현재 시간을 now라고 할 때, x[i] < now라면 now를 y[i]만큼 증가시킵니다.
그렇지 않은 경우에는 now를 x[i] + y[i]로 갱신시키면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
vector<p> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i].x >> v[i].y;

	sort(v.begin(), v.end());
	int ans = 0;

	for(auto i : v){
		if(i.x < ans) ans += i.y;
		else ans = i.x + i.y;
	}

	cout << ans;
}