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

문제 출처: https://www.acmicpc.net/problem/14469

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

 

1. 입력

: 첫 줄에 100 이하의 양의 정수 N이 주어진다.

: 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다.

: 각각 1,000,000 이하의 양의 정수이다.

 

2. 출력

: 모든 소가 농장에 입장하는 데 걸리는 최소 시간을 출력한다.

 

3. 풀이

: 우선 빨리 도착한 소부터 들어갈 수 있도록 해야하고, 만약 동시에 들어온다면 검문시간이 짧은 소부터 지나가야 한다.

: 소의 도착 시간과 검문 소요 시간을 저장할 수 있는 클래스를 만들고 도착 시간과 소요시간을 기준으로 정렬할 수 있도록 Comparable을 구현한다.

: 입력을 저장하고 정렬시킨다.

: 정렬된 소들을 순회하면서 현재 시간이 도착 시간보다 작으면 소가 도착하고나서 검문이 가능하므로 현재시간을 검문시간으로 만들고 소요시간을 더해준다.

: 만약 현재시간이 도착 시간보다 늦다면 그냥 검문 소요 시간을 더해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static class Cow implements Comparable<Cow>{
		int start, time;

		public Cow(int start, int time) {
			super();
			this.start = start;
			this.time = time;
		}

		@Override
		public int compareTo(Cow o) {
			if(this.start != o.start) return this.start-o.start;
			return this.time - o.time;
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		Cow[] c = new Cow[N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());
			
			c[i] = new Cow(start, time);
		}
		
		Arrays.sort(c);
		
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			Cow cur = c[i];
			if(cur.start > cnt) cnt = cur.start + cur.time;
			else cnt += cur.time;
		}
		System.out.println(cnt);
	}
}