[BOJ][Java] 백준 1826번: 연료 채우기
1일 1PS 27일차!
📚 문제
골드 2
- 연료를 계속 소모할 필요 없이 총 연료량이 마을까지의 거리가 되면 된다.
- 이때 현재 연료량으로 갈 수 있는 주유소들 중에서 가장 많이 충전할 수 있는 값이 필요하기에 보유 gas 양으로 maxHeap 을 구성한다.
💡 포인트
- 먼저 거리 순서대로 정렬한다.
- 현재 gas 로 갈 수 있는 주유소들의 gas 양을 maxHeap 에 넣는다.
- 만약 마을에 도착하지 못했을 때 maxHeap 에서 poll 해 gas 를 채워 넣는다.
💻 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class n1826 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] gasStation = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
gasStation[i][0] = Integer.parseInt(st.nextToken());
gasStation[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(gasStation, Comparator.comparingInt(arr -> arr[0]));
st = new StringTokenizer(br.readLine());
int town = Integer.parseInt(st.nextToken());
int gas = Integer.parseInt(st.nextToken());
PriorityQueue<Integer> maxHeap = new PriorityQueue(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return - Integer.compare(o1, o2);
}
});
System.out.println(gasInjection(gas, town, gasStation, maxHeap));
}
private static int gasInjection(int gas, int town, int[][] gasStation, PriorityQueue maxHeap) {
int index = 0;
int cnt = 0;
while (gas < town) {
while(index < gasStation.length && gasStation[index][0] <= gas){
maxHeap.add(gasStation[index][1]);
index++;
}
if (maxHeap.isEmpty()){
return -1;
}
gas += (Integer) maxHeap.poll();
cnt++;
}
return cnt;
}
}
댓글남기기