[BaekJoon] 1826 연료 채우기

1.  문제 링크

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

2.  문제

요약

• 성경이는 트럭은 1km를 가는데 1L의 연료가 새 나가게 되어서, 가장 가까운 마을에 가려고 합니다.
• 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있는데 주유소에서 멈추는 횟수를 최소화하려고 합니다.
• 성경이의 트럭의 연료 탱크에는 연료의 제한이 없이 많이 넣을 수 있습니다.
• 각 주유소의 위치와 각 주유소에서 얻을 수 있는 연료의 양이 주어졌을 때, 주유소에서 멈추는 횟수를 구하는 문제입니다.
• 정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있으며, 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있습니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 주유소의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 주유소의 정보가 주어집니다. 두 개의 정수 a, b로 이루어져있는데, 1보다 크거나 같고 1,000,000보다 작거나 같은 a는 성경이의 시작 위치에서 주유소까지의 거리를 나타내고, 1보다 크거나 같고 100보다 작거나 같은 b는 그 주유소에서 채울 수 있는 연료의 양을 나타냅니다. N + 2번째 줄에 두 정수 L과 P가 주어지는데, 1보다 크거나 같고 1,000,000보다 작거나 같은 L은 성경이의 위치에서 마을까지의 거리를 나타내고 1보다 크거나 같고 1,000,000보다 작거나 같은 P는 트럭에 원래 있던 연료의 양을 나타냅니다.
• 출력: 첫 번째 줄에 주유소에서 멈추는 횟수를 출력합니다. 만약 마을에 도착하지 못할 경우 -1을 출력합니다.

3.  소스코드

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 Main {
    static int N;
    static PriorityQueue<Station> stations;
    static int endPosition, fuel;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        stations = new PriorityQueue<>();

        for(int idx = 0; idx < N; idx++) {
            int distance = scanner.nextInt(), fuel = scanner.nextInt();
            stations.offer(new Station(distance, fuel));
        }

        endPosition = scanner.nextInt();
        fuel = scanner.nextInt();
    }

    static void solution() {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

        int answer = 0;
        while(fuel < endPosition) {
            while(!stations.isEmpty() && stations.peek().distance <= fuel) {
                queue.offer(stations.poll().fuel);
            }

            if(queue.isEmpty()) {
                System.out.println(-1);
                return;
            }

            answer++;
            fuel += queue.poll();
        }

        System.out.println(answer);
    }

    static class Station implements Comparable<Station> {
        int distance, fuel;

        public Station(int distance, int fuel) {
            this.distance = distance;
            this.fuel = fuel;
        }

        @Override
        public int compareTo(Station s) {
            if(distance != s.distance) return distance - s.distance;
            return s.fuel - fuel;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 주유소를 나타내는 Station 클래스를 정의합니다.
  • 시작 위치에서 주유소까지의 거리를 나타내는 변수 distance와 주유소에서 채울 수 있는 연료의 양을 나타내는 변수 fuel을 멤버 변수로 갖습니다.
  • 이후에 주유소를 정렬할 것이기 때문에 정렬 기준을 정하기 위해 Comparable 인터페이스를 구현합니다.
    • distance 기준 오름차순으로, 만약 distance가 같다면 fuel 기준 내림차순으로 정렬합니다.

• 주어진 주유소 정보들을 이용하여 PriorityQueue에 Station 객체들을 넣습니다.
• 현재 남은 연료로 갈 수 있는 주유소들에서 얻을 수 있는 연료의 양들을 담을 PriorityQueue queue를 생성합니다. queue는 내림차순으로 정렬됩니다.
• 성경이의 트럭이 있는 연료의 양을 fuel이라고 했을 때, fuel이 마을까지의 거리보다 크거나 같아지기 전까지 아래 작업을 반복합니다.
  • 방문할 주유소가 남아있고 해당 주유소까지의 거리가 현재 남은 연료보다 작거나 같을 때까지, 즉 해당 주유소를 방문할 수 있을 때까지 queue에 해당 주유소에서 얻을 있는 연료의 양을 넣습니다.
  • queue가 비어있다면 아직 마을에 도착하지 못했는데 더이상 방문할 수 있는 주유소가 없다는 뜻이므로 더이상 연료를 얻지 못해 마을에 도착할 수 없기 때문에 -1을 출력합니다.
  • queue가 비어있지 않다면 하나의 주유소에 멈춰 연료를 얻을 것이기 때문에 멈춘 주유소의 개수를 나타내는 변수 answer의 값을 1 증가시키고 fuel에 queue에서 뽑은 값을 추가해줍니다.
    • 얻을 수 있는 연료 중 가장 많은 연료를 얻어야 더 많은 거리를 이동하여 멈추는 횟수를 줄일 수 있기 때문에 queue를 내림차순으로 정렬하였습니다.
• 위 과정에서 -1을 출력하지 않았다면 마을에 도착할 수 있다는 뜻이므로 answer 값을 출력합니다.