[Java] 1826번 - 연료 채우기

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

1826번: 연료 채우기

 

 

🚗 문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

 

🚗 입력

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, P(1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.

 

 

🚗 출력

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

 

 

🚗 예제 입력 & 출력

예지 입력(왼쪽), 예제 출력(오른쪽)

 

 

 

🚗 설명

우선순위 큐를 사용하여 풀 수 있는 문제이다.

 

주유소 위치(station)와 해당 주유소에서 얻을 수 있는 연료(fuel)를 포함한 class를 오름차순으로 저장하는 우선순위큐(info)를 생성한다. 항상 거리순으로 주유소 위치 정보가 주어지지 않기 때문이다.

 

현재 가지고 있는 연료만큼 갈 수 있는 주유소 중에서 가장 연료의 양이 많은 주유소를 방문해야 한다.

그렇기 때문에 연료의 양을 우선순위 큐에서 많은 순서대로 정렬하는 우선순위 큐가 필요하다.

 

2개의 while문을 사용하여 구현한다.

 

첫번째 while문은, 현재 보유하고 있는 연료의 양이 총 거리보다 작을 때 계속 반복한다.

즉, 최종 지점에 도달하면 while문 탈출.

 

두번째 while문은, 갈 수 있는 주유소가 존재하고, 현재 보유하고 있는 연료로 해당 주유소까지 갈 수 있을 때,

해당 주유소에서 얻은 연료를 연료의 양 우선순위 큐(queue)에 추가한다.

주유소 하나를 방문(poll)하고 이동 가능한 거리(currentFuel)를 증가시킨다. 또한 방문하였기 때문에, result도 1을 더해준다.

 

 

 

 

 

 

 

🚗 코드 구현 (Java)

import java.util.*;
import java.io.*;

class Station implements Comparable<Station> {
    int station;
    int fuel;
    public Station(int station, int fuel) {
        this.station = station;
        this.fuel = fuel;
    }
    
    @Override
    public int compareTo(Station o) {
        return this.station - o.station;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());  // 주유소 갯수
        PriorityQueue<Station> info = new PriorityQueue<Station>();  // 주유소에 대한 정보 담을 우선순위 큐
        String[] s;
        
        // 주유소 정보를 우선순위 큐에 저장
        for(int i=0 ; i < N ; i++) {
            s = br.readLine().split(" ");
            int stationLocation = Integer.parseInt(s[0]);
            int fuel = Integer.parseInt(s[1]);
            info.add(new Station(stationLocation, fuel));
        }
        
        s = br.readLine().split(" ");
        
        // 마을까지 거리
        int totalDistance = Integer.parseInt(s[0]);
        
        // 현재 가지고 있는 연료의 양
        int currentFuel = Integer.parseInt(s[1]);
        
        // 방문한 주유소의 갯수
        int result = 0;
        
        // 가장 큰 연료 순으로 내림차순
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        while(currentFuel < totalDistance) {
        
            while(!info.isEmpty() && currentFuel >= info.peek().station) {
                
                Station tmp = info.poll();
                queue.add(tmp.fuel);
            }
            
            if(queue.isEmpty()) {
                result = -1;
                break;
            }
            
            currentFuel += queue.poll();
            result++;
        }
        System.out.println(result);
    }
}