백준 알고리즘 1826번: 연료 채우기

문제 정보

---

 

1826번: 연료 채우기

 

핵심

---

선뜻 Greedy를 사용하기 애매했다. 바로 직전 문제인 주유소(13305번) 보다 더 어려웠던 것 같다.

내가 그리디에 아직은 익숙하지 않다고 생각했다.

 

문제의 내용

문제는 단순하다. 시작 지점에서 끝 지점까지 이동할 때, 주유소를 최소 횟수만큼 들리도록 하는 것이다.

각 가중치는 해당 주유소에서 넣을 수 있는 기름 양이다.

 

실수했던 내용

난 처음에 이 문제의 유형을 인지하지 못하고, 목적지까지 가는 중간 경로들(멈추는 곳)을 주유소라고 당연히 생각해왔다.

생각해야 할 것들이 너무 많았고, 이렇게 된다면 모든 주유소들 중 특정 주유소를 방문하는 모든 경우의 수를 구해야 하기 때문에 비효율적이라고 생각이 들어 그만두었다

 

생각해야 하는 점

그냥 가자. 조금 생각을 다르게 해보고 넓게 바라보는 습관을 들이자.

주유소에서 멈춘다고 생각하지 말고, 일단 기름이 있는 만큼 이동해 보자

 

(예제 1 기준) 처음 주어진 기름의 양은 10이다. 따라서 10만큼 일단 간다.

그리고, 지나온 주유소들을 바라본다. 주유소들 중에서 내가 가장 이득볼 수 있는 주유소(주유할 수 있는 양이 많은 주유소)를 선택한다.

현재 상태에서는 거리가 4만큼 떨어진 주유소에서 4만큼의 기름을 넣는 것이 좋아보이므로, 선택한다. 그리고 이동한다

 

4만큼의 기름으로 2번 위치에 도착했다.

더 이상 기름이 없으니, 지나온 주유소들을 바라보며 가장 많이 주유할 수 있는 11 위치에 있는 주유소에서 5만큼의 기름을 넣는다.

그리고 이동한다.

 

5만큼의 기름으로 3번 위치에 도착했다. 또 이제 기름을 넣어야 하니, 지나온 주유소들을 보며 최적의 주유소를 찾자.

이번에는 15 위치에 있는 주유소에서 10만큼의 기름을 넣으면 될 것 같다

 

이제 도착 지점을 넘어 무사히 도착할 수 있었다.

지금 이렇게 구한 경우가 최소의 주유소를 방문하여 도착한 경우가 된다. 우리는 각 상황에서 할 수 있는 최선을 다했기 때문이다.

 

결론

일단 먼저 이동하고, 지나온 주유소들을 우선순위 큐에 집어넣는다(넣을 수 있는 기름 양 순(내림차순))

그중 하나를 빼고(최대값) 내 위치를 이동시킨다. 이동하면서 지나온 주유소를 우선순위 큐에 집어넣는다.

위 내용을 반복하면서, FIN 위치 이상으로 이동했거나 더이상 주유할 곳이 없으면 종료한다.

 

풀이

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        Queue<Station> stations = new PriorityQueue<>((o1, o2) -> o1.distance-o2.distance);

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            stations.add(new Station(Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())));
        }
        st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        int currentDistance=P;
        int result = 0;
        Queue<Station> pastStations = new PriorityQueue<>(((o1, o2) -> o2.fuel - o1.fuel));
        while(!stations.isEmpty() && currentDistance < L) {
            while(!stations.isEmpty() && stations.peek().distance <= currentDistance) {
                pastStations.add(stations.poll());
            }
            if(pastStations.isEmpty()) {
                break;
            }
            currentDistance += pastStations.poll().fuel;
            result++;
        }
        System.out.println(currentDistance >= L ? result : -1);
    }
}
class Station {
    public int distance;
    public int fuel;

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

 

 

Source Code on GitHub

---