[백준] 1826 연료 채우기 [자바]

 

---

https://www.acmicpc.net/board/view/79605

글 읽기 - 테케 몇개 남깁니다.

https://nato-blog.tistory.com/102

[백준] 1826 - 연료 채우기

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;
class Heap {
	int[] arr;
	int index;
	public Heap(int N) {
		arr = new int[N];
		index = 0;
	}
	public void add(int n) {
		arr[index] = n;
		addHeapify(index);
		index++;
	}
	public int poll() {
		if(index == 0)
			return -1;
		int result = arr[0];
		arr[0] = arr[--index];
		pollHeapify(0);
		return result;
	}
	public void addHeapify(int idx) {
		int parent = (idx - 1) >> 1;
		if(parent < 0)
			return;
		if(arr[idx] > arr[parent]) {
			swap(idx, parent);
			addHeapify(parent);
		}
	}
	public void pollHeapify(int idx) {
		int p = idx;
		int l = (idx << 1) + 1;
		int r = (idx << 1) + 2;
		if(l < index && arr[p] < arr[l]) {
			p = l;
		}
		if(r < index && arr[p] < arr[r]) { 
			p = r;
		}
		if(p != idx) {
			swap(idx, p);
			pollHeapify(p);
		}
	}
	public void swap(int a,int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	public int size() {
		return index;
	}
}

public class Main {
	static int[][] dis_oi;
	static int N;
	static int L;
	static int P;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		N = Integer.parseInt(br.readLine());
 		dis_oi = new int[N][2]; //0 거리 1 기름
 		for(int i = 0; i < N; i++) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			dis_oi[i][0] = Integer.parseInt(st.nextToken());
 			dis_oi[i][1] = Integer.parseInt(st.nextToken());
 		}
 		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		L = Integer.parseInt(st.nextToken()); //총 거리
 		P = Integer.parseInt(st.nextToken()); //기본 연료
 		Arrays.sort(dis_oi, (e1, e2) -> {
 			return e1[0] - e2[0];
 		});
 		
 		int j = 0;
 		int cnt = 0;
 		Heap heap = new Heap(N);
 		while(P < L) {
 			while(j < N && P >= dis_oi[j][0]) { //다음 주유소 까지 갈 수 있다면 우선순위 큐에 추가
 				heap.add(dis_oi[j++][1]);
 			}
 			if(heap.size() == 0) { //모든 주유소에 방문했는데 p < L 이면
 				cnt = -1;
 				break;
 			}
 			else { 		//주유소에 방문하고 p연료를 보충(다음 주유소에 갈 수 있을 때 까지 반복)
 				cnt++;
 				P += heap.poll();
 			}
 		}
 		System.out.println(cnt);
 	}
}