[백준 1826번] 연료 채우기

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

연료 채우기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	883	197	145	25.261%

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 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)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력

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

예제 입력 1 

4
4 4
5 2
11 5
15 10
25 10

예제 출력 1 

3

    

알고리즘 스터디에서 힙을 공부하면서 푼 문제이다. 거리를 기준으로 힙 하나, 연료를 기준으로 힙 하나를 만들어서

각 시점의 거리에 맞게 힙을 사용하면 풀 수 있는 문제이다.

직접 만든 heap과 priority_queue stl을 사용해서 풀어봤는데 수행시간은 같았고,

정적할당을 한 heap이 메모리를 덜 소모했다.

1. HEAP

///////////////////////////
//직접 만든 heap STL 사용//
///////////////////////////
#include<iostream>
 
using namespace std;
 
#define DEFAULT_SIZE 10001
 
template <typename T>
class Heap {
public:
    Heap();
    Heap(int);
    ~Heap();
    void insert(const T&);
    void swap(T* a, T* b);
    void print();
    int h_size();
    T top();
    T pop();
private:
    T* heap;
    int capacity;
    int size;
};
 
template <typename T>
Heap<T>::Heap() {
    heap = new T[DEFAULT_SIZE];
    size = 0;
    capacity = DEFAULT_SIZE;
}
 
template <typename T>
Heap<T>::Heap(int Capacity) : capacity(Capacity)
{
    heap = new T[Heap::capacity];
    size = 0;
}
 
template <typename T>
Heap<T>::~Heap()
{
    delete[] heap;
}
 
template <typename T>
void Heap<T>::swap(T* a, T* b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}
 
template <typename T>
void Heap<T>::insert(const T& data)
{
    int usedPos = size;
    int parentPos = (usedPos - 1) / 2;
 
    if (size == capacity)
    {
        cout << "Full Heap\n";
        return;
    }
 
    heap[size] = data;
 
    while (usedPos >= 0 && heap[usedPos].second > heap[parentPos].second) {
        swap(&heap[usedPos], &heap[parentPos]);
        usedPos = parentPos;
        parentPos = (usedPos - 1) / 2;
    }
 
    size++;
}
 
template <typename T>
T Heap<T>::top() {
    if (size == 0) return{ 0,0 };
    else return heap[0];
}
 
template <typename T>
T Heap<T>::pop()
{
    if (size == 0) return{ 0,0 };
 
    int selectChild = 0;
    int parentPos = 0;
    int leftPos = 1;
    int rightPos = 2;
    T value = heap[0];
 
    size--;
    heap[0] = { 0,0 };
    swap(&heap[0], &heap[size]);
    while (1) {
        if (leftPos >= size) break;
        else if (rightPos >= size) selectChild = leftPos;
        else selectChild = heap[leftPos].second < heap[rightPos].second ? rightPos : leftPos;
 
        if (heap[selectChild].second > heap[parentPos].second)
        {
            swap(&heap[parentPos], &heap[selectChild]);
            parentPos = selectChild;
        }
        else break;
 
        leftPos = 2 * parentPos + 1;
        rightPos = leftPos + 1;
    }
 
    return value;
}
 
template <typename T>
void Heap<T>::print()
{
    for (int i = 0; i < size; i++) {
        cout << heap[i] << " ";
    }
    cout << "\n";
}
 
template <typename T>
int Heap<T>::h_size() {
    return size;
}
 
int N, a, b, L, P;
int position, i, cnt;
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    Heap<pair<int, int>> H;
    Heap<pair<int, int>> S;
 
    cin >> N;
 
    for (i = 0; i<N; i++) {
        cin >> a >> b;
        S.insert({ b,-a });
    }
 
    cin >> L >> P;
 
    position = P;
 
    while (1) {
        if (position >= L) break;
 
        while (1) {
            if (S.h_size() == 0) break;
 
            if (-S.top().second <= position) {
                H.insert({ -S.top().second,S.top().first });
                S.pop();
            }
            else break;
        }
 
        if (H.h_size() == 0) {
            cnt = -1;
            break;
        }
 
        P = H.pop().second;
        position += P;
        cnt++;
    }
 
    cout << cnt;
}

2. priority_queue STL

///////////////////////////
//priority_queue STL 사용//
///////////////////////////
#include<iostream>
#include<queue>
 
using namespace std;
 
bool operator<(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}
 
priority_queue<int> H;
priority_queue<pair<int, int>> S;
 
int N, a, b, L, P;
int position, i, cnt;
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N;
 
    for (i = 0; i<N; i++) {
        cin >> a >> b;
        S.push({ -a,b });
    }
 
    cin >> L >> P;
 
    position = P;
 
    while (1) {
        if (position >= L) break;
 
        while (1) {
            if (S.size() == 0) break;
 
            if (-S.top().first <= position) {
                H.push(S.top().second);
                S.pop();
            }
            else break;
        }
 
        if (H.size() == 0) {
            cnt = -1;
            break;
        }
 
        P = H.top();
        H.pop();
        position += P;
        cnt++;
    }
 
    cout << cnt;
}