(백준) 연료채우기_1826 [java]

https://www.acmicpc.net/problem/1826

 

🐢 설명

일직선의 경로에서 시작점이 0일때 오른쪽의 어딘가에 있는 목적지까지 가야하는 문제이다.

 

이때 출발지점에서 갈 수 있는 최대 거리는 연료량과 동일하고, 중간에 주유소에 들려서 연료량을 더할 수 있다. 이때의 충전 회수를 최소로 해서 목적지에 도달하도록 하면 된다.

 

먼저 우선순위 큐 두개를 사용한다.

1. 거리큐 : 갈 수 있는 모든 주유소를 가까운 거리 순으로 담을 큐
2. 연료큐 : 주유소를 담은 큐에서 갈 수 있는 거리내에 있다면 연료량을 많은 순으로 담을 큐

거리큐의 모든 주유소는 가까운 순으로 정렬되어 있으므로 자신이 갈 수 있는 주유소들에 대해서만 루프를 돌면서 연료큐에 모두 넣어준다.

연료큐의 최상단 값을 현재 연료 량에 더해준다. 이 값은 한번에 가장 많은 연료를 충전할 수 있는 값이다.

 

해당 행위를 현재의 연료량이 목적지보다 커질때까지 반복한다.

 

종료조건으로는 두가지가 있다.

1. 거리큐도 비어있고 연료큐도 비어있다면 더이상 갈 수 없으므로 탐색을 종료한다.
2. 연료큐는 비어있고, 거리큐의 최상단 값(가장 가까운 주유소)가 현재 연료량보다 크다면 (못가는 거리) 탐색을 종료한다.

 

🐢코드

public class 연료채우기_1826 {
    static int N, END, currentFuel;
    static PriorityQueue<FUEL> distQ = new PriorityQueue<>(Comparator.comparingInt(f -> f.dist));
    static PriorityQueue<Integer> fuelQ = new PriorityQueue<>(Comparator.comparingInt(o -> -o));

    private static class FUEL {
        int dist, quantity;

        public FUEL(int dist, int quantity) {
            this.dist = dist;
            this.quantity = quantity;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int dist = Integer.parseInt(st.nextToken());
            int quan = Integer.parseInt(st.nextToken());
            distQ.add(new FUEL(dist, quan));
        }
        st = new StringTokenizer(br.readLine());
        END = Integer.parseInt(st.nextToken());
        currentFuel = Integer.parseInt(st.nextToken());

        solve();
    }

    private static void solve() {
        int answer = 0;

        while (END > currentFuel)
        {
            // 연료도 없고, 주유소도 없음
            if (fuelQ.isEmpty() && distQ.isEmpty()) {
                answer = -1;
                break;
            }

            // 연료없고, 주유소 못감
            if (fuelQ.isEmpty() && distQ.peek().dist > currentFuel) {
                answer = -1;
                break;
            }

            // 갈 수 있는 주유소 담기
            while (!distQ.isEmpty() && distQ.peek().dist <= currentFuel) {
                fuelQ.add(distQ.poll().quantity);
            }

            // 연료 충전
            if (!fuelQ.isEmpty()) {
                currentFuel += fuelQ.poll();
                answer++;
            }
        }
        System.out.println(answer);
    }
}

🐢 마무리