[BOJ] 1826 : 연료 채우기

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

---

그리디 탐색

[ 문제해석 ]

 

 아래와 같은 2가지 이유 때문에 연료를 중심으로 그리디하게 접근해야 된다.

 

 1) 현재 가지고 있는 연료 = 현재 내가 갈 수 있는거리

 내가 현재 나갈 수 있는 거리는 내 거리에서 가지고 있는 연료만큼 이동할 수 있다. 따라서, 연료랑 내가 갈 수 있는 거리는 동일한 의미로 해석할 수 있다!

 

 2) 주유소 연료 + 현재 가지고 있는 연료 = 주유소 들려서 갈 수 있는 거리

 내가 현재 가지고 있는 연료로 갈 수 있는 주유소가 K개 있다고 해보자. 어차피 K개의 주유소는 내가 지금 다 들릴 수 있고 우리는 도착 지점까지 주유소를 적게 들리고 이동해야 한다.

 --> 이왕 주유소에 들릴 거면 들렸을 때 가장 멀리 갈 수 있는 주유소에 들리는 게 좋다!

 --> 주유소에서 얻을 수 있는 연료 + 내가 가지고 있는 연료 = 주유소에 들려서 갈 수 있는 거리이므로 들릴 수 있는 주유소 중에서 연료가 제일 많은 곳이 의미가 있다!

 

예를 들어, 내가 연료가 10인 상태에서 시작하고 (2,4) / (6,5) 에 주유소가 있다고 하자. 
(2, 4) 주유소는 연료를 2만 쓰고 4를 얻을 수 있고, 
(6, 5) 주유소는 연료를 6이나 쓰고 5를 얻을 수 있으므로 (2,4) 가 더 유리해 보인다.
--> 이게 함정!! 
(2, 4) 를 들리면 연료가 12가 남고 (6, 5) 를 들리면 연료가 9 가 남지만  
실제로 (2, 4)를 들리면 나는 최대 14까지 갈 수 있고 (6, 5)를 들리면 나는 최대 15까지 갈 수 있음 
--> 내가 갈 수 있는 주유소 중에서 연료를 제일 많이 주는 주유소들을 계속 탐색해야됨! 

 

[ 알고리즘풀이 ]

 

 L = 도착지점

 curL = 현재 연료양 = 현재 갈 수 있는 거리

 ans = 주유소 들린 횟수

 curP = 현재 연료양으로 갈 수 있는 주유소 인덱스

  

 0) 현재 연료양으로 도착지점에 갈 수 있는지 체크한다. (curL < L)

 1) 도착할 수 없다면, priority_queue 를 이용해서 현재 갈 수 있는 주유소의 연료를 다 push한다.

 2) 우리는 어차피 갈 수 있는 주유소 중에서 연료를 제일 많이 주유소가 필요!

 --> 가장 연료를 많이 주는 주유소를 들리자.
 --> curL += pq.top(); ( 가장 많이 주는 주유소에 들려 연료 충전! )

 --> ans++;  ( 주유소에 방문함 )

 3) 0~2) 과정을 반복한다! 이때, 모든 주유소를 방문해봐서 priority_queue 가 비었는데도 도착지점에 도착할 수 없다면 -1 을 출력한다.

 

[ 코드 C++ ]

#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, L, P;
    pair<int, int> gasStation[10000];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> gasStation[i].first >> gasStation[i].second;
    cin >> L >> P;
 
    sort(gasStation, gasStation + N);
 
    // P연료를 가지고 L까지 가야된다!
    priority_queue<int> pq;
 
    int curP = 0, curL = P, ans = 0;
    while (curL < L) {
        while (curP < N && gasStation[curP].first <= curL) {
            pq.push(gasStation[curP++].second);
        }
        if (pq.empty()) { // L 에 도착도 못했고, 더 이상 갈 곳도 없음.
            ans = -1;
            break;
        }
        curL += pq.top();
        pq.pop();
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1826.cpp

travelbeeee/ProblemSolving

---