[Baekjoon] 14469_소가 길을 건너간 이유 3

Silver IV

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

---

< 소가 길을 건너간 이유 3 >

 

문제 풀이 

 

우선순위 큐를 사용해서 문제를 해결한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _14469_ { // 소가 길을 건너간 이유 3

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			queue.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
		}

		int result = 0;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();

			if(temp[0]<=result) {
				result+=temp[1];
			}else {
				result=temp[0]+temp[1];
			}
		}
		System.out.println(result);
	}
}

변수)
n : 양의 정수
queue : 우선순위 큐 [소의 도착 시간, 검문 시간]
result : 모든 소가 농장에 입장하는데 걸리는 최소 시간

 

양의 정수만큼 소의 도착 시간과 검문 시간을 입력받아 우선순위 큐에 저장한다. 그 후 차례대로 우선순위 큐에서 꺼낸다. result 보다 소의 도착 시간이 적거나 같다면 소가 검문을 받을 수 있으므로 검문 시간을 더해준다. result보다 크다면 소가 도착할 때까지 기다려야 하므로 기다렸다가 검문 시간도 더해준다.

---

---