[백준] 1826번 연료 채우기 (C++)

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

 

 

이 문제는 N개의 주유소가 주어지며 각각의 주유소에 대한 정보(시작 위치에서 주유소까지의 거리, 채울 수 있는 연료의 양)이 주어지며

 

마지막 줄에는 도착지점까지의 거리, 연료의 양이 주어진다.

 

이때 최소한에 주유소에 멈추는 횟수를 출력하며 만약 도착하지 못하는 경우 -1을 출력하는 문제이다.

 

최소한으로 주유소에 멈추는 횟수를 알아야하기 때문에 그리디하게 접근했다.

 

즉 만약 내가 주유소를 도착했다 하더라도 충전을 할지 안할지 선택해야된다는 의미이다.

 

이를 구현하기 위해서 주유소를 시작위치를 오름차순 순으로 정렬한 이후 최대힙을 사용하였다.

 

필자의 방법은 이러하다.

 

for문을 사용하여 주유소를 순회하되 주유소에 도착한다해도 바로 연료를 충전하지 않고 최대힙에 담아둔다.

 

이때 주유소를 다 순회하지 못하는 경우 우선순위 큐에서 하나씩 꺼내어 도착할 수 있는지 확인하였다.

 

이후 도착거리 지점까지도 마찬가지로 우선순위 큐에서 하나씩 꺼내 도착하는지 확인하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 0};
int dy[] = {0, 1};
int N, L, P;
vector<pii> v;
priority_queue<int> pq;

void Print() {
    for(auto it : v) {
        cout << it.first << " " << it.second << endl;
    }
}

void solve() {
    if(L <= P) {
        cout << 0;
        return;
    }

    sort(v.begin(), v.end());

    int gas = P;
    int answer = 0;
    int located = 0;
    for(int i = 0; i < N; i++) {
        int locate = v[i].first;
        int gasAddit = v[i].second;

        if(gas <= locate) {
            while(!pq.empty() && gas <= locate) {
                gas += pq.top();
                pq.pop();
                answer++;
            }

            if(gas < locate) {
                cout << -1;
                return;
            }
        }
        pq.push(gasAddit);
    }

    while(!pq.empty() && gas < L) {
        gas += pq.top();
        pq.pop();
        answer++;
    }

    if(gas >= L) {
        cout << answer;
    }
    else cout << -1;
}

void input() {
    cin >> N;

    for(int i = 0;  i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});        // 위치, 채울 수 있는 양
    }

    cin >> L >> P;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}