[PS] BOJ1826 연료 채우기 ( Greedy ) with JAVA

1826번: 연료 채우기

 

 

◎ 문제풀이

 

 

 

문제를 풀려면 우선순위큐 두 개를 사용해야 한다.

 

입력받은 주유소는 우선순위큐에 저장하고 거리를 기준으로 오름차순하여 정렬한다. 

오름차순으로 정렬해야 현재 자동차 주유량을 기준으로 주유소에 차례로 접근이 가능하다. 

 

현재 자동차 주유량이 10L라고 해보자. 

10L로 접근가능한 주유소를 우선순위큐에서 하나씩 꺼낸다.

주유소의 주유량을 주유량 우선순위큐에 저장한다.

 

 

 

 

주유량 우선순위큐는 내림차순이다.

주유량 우선순위큐에서 주유량을 하나 꺼내어 연료를 주입한다. (5L)

그럼 현재 주유량은 15L(10+5)이다. 

 

여기서 주유량은 현재 자동차 연료를 의미하지 않는다.

자동차가 갈 수 있는 거리를 의미한다. 

15L이면 15km를 갈 수 있다는 의미이다. 

마을이 25km 거리에 있다면 연료를 더 주입해야 한다.

 

다시 주유소에 접근해보자. 

현재 주유량이 15L이므로 접근가능한 주유소 범위도 늘어났다.

 

 

 

주유량 우선순위큐에서 주유량을 하나 꺼내어 연료를 주입한다. (10L)

그럼 현재 주유량을 25L이다.

 

25L는 25km를 갈 수 있다는 의미이다.

마을도 25km 거리에 있다. 

 

그러므로 두 번의 주유로 마을까지 도착할 수 있다. 

 

그럼 이를 코드로 구현해보자. 

 

 

◎ 코드

package org.example.greedy;


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

import static java.lang.Math.min;

//BOJ1826 연료 채우기 ( 우선순위큐 사용 )
public class Greedy19_2 {

    public static StringTokenizer st;
    public static int n,target, currGas;
    public static int ans = 0;
    public static PriorityQueue<GasStation> gasStationQueue = new PriorityQueue<>();
    public static PriorityQueue<Integer> gasQueue = new PriorityQueue<>( (i1,i2) -> i2-i1 );

    public static class GasStation implements Comparable<GasStation>{
        public int des;
        public int gas;

        public GasStation(int des, int gas){
            this.des = des;
            this.gas = gas;
        }

        @Override
        public int compareTo(GasStation g){
            return this.des - g.des;
        }
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            int des = Integer.parseInt(st.nextToken());
            int gas = Integer.parseInt(st.nextToken());

            gasStationQueue.add(new GasStation(des,gas));
        }

        st = new StringTokenizer(br.readLine());
        target = Integer.parseInt(st.nextToken()); // 트럭과 마을 사이의 거리
        currGas = Integer.parseInt(st.nextToken()); // 트럭 초기 연료량

        // 현재주유량 < 마을거리
        while( currGas < target ){

            while(!gasStationQueue.isEmpty() && gasStationQueue.peek().des <= currGas ){
                gasQueue.add( gasStationQueue.poll().gas);
            }

            // 더이상 주유소가 없으면 -1
            if(gasQueue.isEmpty()) {
                ans = -1;
                break;
            }

            // 주유하기 
            ans++;
            currGas += gasQueue.poll();
        }

        System.out.println(ans);


    }





}