[백준 1826] 연료 채우기

요구사항

1. 주유소에 최소한의 횟수만 들려서 마을에 도착하기

 

풀이

주어지는 입력 L과 P를 

주유소-마을까지의 거리 L

내가 이미 간 거리 P

라고 생각하면 쉽게 풀 수 있는 문제 인듯 한다.

 

 

1. 이미 dist만큼 이동 한 후, dist까지 이동하면서 들릴 수 있는 주유소의 기름 양을 우선 순위 큐에 넣어 준다.

2. 제일 많은 기름을 가지고 있는 기름 양 만큼 넣어준다(cnt++)

3. 다시 1번 과정을 반복한다

 

dist가 goal 만큼 왔을때 or 큐가 비었을때 멈춰서 정답을 출력한다

뭔가 두번 꼬아져 있는 문제인거 같다

 

#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
};
int n;
go map[10100];
int goal, dist;
bool com(go a, go b) {
	if (a.x < b.x) return true;
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &map[i].x, &map[i].y);
	}
	int GasStation = 0;
	int cnt = 0;
	priority_queue<int> q;
	scanf("%d%d", &goal, &dist);
	sort(map, map + n,com);
	while (true) {
		if (dist >= goal) break;
		for (int i = GasStation; i < n; i++) {
			if (map[i].x <= dist) {
				q.push(map[i].y);
				GasStation++;
			}
			else {
				break;
			}
		}
		if (q.empty())
			break;
		dist = dist + q.top();
		cnt++;
		q.pop();
	}
	if (dist >= goal) {
		cout << cnt << endl;
	}
	else {
		cout << -1 << endl;
	}
}