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

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

1826번: 연료 채우기

1. 주의할 점

- 입력 받는 주유소의 정보가 거리순이 아니다

 

2. 구현

- 주유소의 정보를 우선순위 큐 PQ2에 입력받는다(거리순으로 오름차순 정렬)

- While문 시작

- 현재 보유한 연료로 목적지에 도달 할 수 있다면 While문을 끝낸다

- 현재 보유한 연료로 갈 수 있는 모든 주유소를 우선순위 큐 PQ에 넣는다(충전할 수 있는 연료순으로 내림차순 정렬)

- PQ가 비어있다면 Result = -1로 바꾸고 While문을 끝낸다

- PQ에서 1개 씩 Pop하면서 위의 과정을 반복한다

- While문 끝

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int num;
bool check[10000] = { false, };
struct info {
	int dist, oil;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.oil < b.oil;
	}
};
struct cmp2 {
	bool operator()(info &a, info &b) {
		return a.dist > b.dist;
	}
};
info tmp;
priority_queue<info, vector<info>, cmp> pq;
priority_queue<info, vector<info>, cmp2> pq2;

int main() {
	int dist, val, destination, fuel, result = 0;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> dist >> val;
		tmp.dist = dist;
		tmp.oil = val;
		pq2.push(tmp);
	}
	cin >> destination >> fuel;

	while (fuel < destination) {
		//보유한 연료로 갈 수 있는 주유소 다 넣는다
		while (!pq2.empty() && fuel >= pq2.top().dist) {
			tmp.dist = pq2.top().dist;
			tmp.oil = pq2.top().oil;
			pq.push(tmp);
			pq2.pop();
		}
		if (pq.empty()) {
			result = -1;
			break;
		}
		int supp = pq.top().oil;
		pq.pop();
		fuel += supp;
		result++;
	}
	cout << result;
	system("pause");
	return 0;
}