(BOJ) 1826 연료채우기

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

https://github.com/huhsay/algorithm/blob/master/heap/src/BOJ_1826.java

TIPS

우선순위큐(힙)

ALGORITHM

두개의 우선순위 큐를 사용합니다.

먼저 입력값을 받으며, 거리를 기준으로 가까운 주유소를 정렬합니다. (stations)

while문으로 내가 갈 수 있는 거리가 목표지점에 미치지 못한다면 목표지점을 찾을 때까지 반복하도록 합니다.

while문 안에서 현재 내가 도달할수 있는 범위에 있는 주유소가 있다면

stations 배열에서 객체를 꺼내어 새로운 우선순위 큐에 넣습니다.(reachableStations)

reachableStation은 연료가 많은 순으로 정렬됩니다.

만약 reachableStation에 객체가 없다면 목적지에 도달할 수 없습니다.

reachableStations에서 객체를 꺼내어(제일 연료가 많은 곳)

그곳으 현재위치보다 멀리있다면 움직이는 거리를 계산하고

현재 위치보다 이전이이라면 연료만 채워줍니다.

KEY POINT

현재 위치에서 항상 가장 많은 연료를 얻을 수 있는 주유소에 방문합니다.

가장 먼 위치에서 더이상 앞으로 갈 곳이 없다면 뒤로 돌아가는 경우가 생기게 됩니다.

처음엔 이런 경우들을 생각하려면 현재 위치를 업데이트 한 겂을 이전으로 돌려야 한다고 생각했습니다.

하지만 문제에서 물어보는 것은 경로가 아니기 때문에 항상 많은 연료를 주유소를 방문하는 것이 좋다는 것을 주의 해야 합니다.

이전 주유소를 들려야한다면 아래의 그림에서 a b c 순으로 주유소를 방문하나 a c b 순으로 방문하나 결과적으로 차이가 없음을 이해하면 좋습니다.

구현한 알고리즘 개념상 C를 먼저 선택하게 됩니다. 

C에 먼저 방문하게 되면 현재 연료는 C에서 얻을 수있는 연료 5를 더하고 움직인 거리 4를 뺀 5입니다.

C위치에서 5칸 더 앞으로 갈 수 있는데 그곳에 주유소가 없다면 B를 선택해야 합니다.

이때 다시 A로 돌아가 B를 선택할 필요 없이 바로 B에서 얻을 수 있는 4를 현재 연료에 더하면 9입니다.

순차적으로 A B C 로 진행 하더라도 9가 나올 것입니다.

B를 먼저 선택했더라도 더 갈수 있는 주유소가 추가 되지 않습니다.

더 멀리갈 수있는 C를 먼저 선택했어도 주유소가 추가 되이 않았기 때문입니다.

LESSON

변수명을 제대로 지으려다가 꼬여서 개념은 이해 했으나 의도한 값이 나오지 않아 시간이 많이 걸렸다.

빠르게 푸는 것도 중요하지만 다른사람이 이해하기 쉬운 코드를 작성하려면 변수 명의 길어도 좋다고 한다.

IDE 들의 성능이 좋아저 자동완성이 가능하기 때문다.

MORE

comparable

Heap

PriorityQueue

CODE

import java.util.*;

/**
 * 백준 1826 연료채우기
 * https://www.acmicpc.net/problem/1826
 * http://bethejustice.tistory.com/8?category=751083
 *
 * 180703
 */

public class BOJ_1826 {
    static int N, L, P;
    static int ans = 0;
    static Queue<Station> stations;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        stations = new PriorityQueue<>(new Comparator<Station>() {
            @Override
            public int compare(Station o1, Station o2) {
                return Integer.compare(o1.location, o2.location);
            }
        });

        int sum = 0;
        for (int i = 0; i < N; i++) {
            int tempL = sc.nextInt();
            int tempV = sc.nextInt();
            stations.add(new Station(tempL, tempV));

            sum += tempV;
        }

        L = sc.nextInt();
        P = sc.nextInt();

        // 모든 주유소를 들리더라도 최정 거리에 도달할 수 없다면 미리 끝냅니다.
        if (sum + P < L) {
            System.out.println(-1);
            return;
        }

        int currentLocation = 0; // 갈 수 있는 가장 먼 주유소의 위치
        int reachableLocation = P;
        int currentPetrol = P;

        Queue<Station> reachableStations = new PriorityQueue<>(new Comparator<Station>() {
            @Override
            public int compare(Station o1, Station o2) {
                return Integer.compare(o1.Petrol, o2.Petrol) * -1;
            }
        });

        Station nextStation;
        while (reachableLocation < L) {

            //범위내 갈 수 있는 주유소를 확인
            while (!stations.isEmpty() && stations.peek().location <= reachableLocation) {
                reachableStations.add(stations.remove());
            }

            //더이상 갈 수 있는 주유소가 없을 경우
            if (reachableStations.isEmpty()) {
                ans = -1;
                break;
            }

            //멈추는 주유소를 추가
            nextStation = reachableStations.remove();
            ans++;

            if (nextStation.location < currentLocation){
                // 가장 먼 주유소보다 이전에 있던 주유소라면 거리와 상관없이 연료만 추가
                reachableLocation += nextStation.Petrol;
                currentPetrol += nextStation.Petrol;
            }else {
                // 다음 멈추는 주유소가 가장 먼 거리라면 이동하면서 사용된 연료 계산
                int usedPetrol = nextStation.location-currentLocation;
                currentLocation = nextStation.location;
                currentPetrol = currentPetrol + nextStation.Petrol - usedPetrol;
                reachableLocation = currentLocation+currentPetrol;
            }
        }

        System.out.println(ans);
    }

    static class Station {
        int location, Petrol;

        Station(int location, int Petrol) {
            this.location = location;
            this.Petrol = Petrol;
        }
    }
}