boj, 백준) 1826. 연료 채우기(C/C++)

1. 문제 링크

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

1826번: 연료 채우기

2. 문제 개요

연료 1L당 1km를 갈 수 있다. 

목적지와 출발지의 위치가 주어진다. 가는 길에는 주유소가 있는데 각 주유소의 위치, 넣을 수 있는 연료의 양이 주어질 때, 최소한의 횟수로 목적지까지 하고자 할 때, 최소 횟수를 구하는 프로그램을 작성하라.

 

3. 문제 힌트

greedy 하게 접근해보자.

현재 내 위치가 주어져 있고 '최소'한의 횟수로 도착하려고 한다.

 

현재 있는 기름으로 최대한 간다고 했을 때, 여러 주유소 중 일부 주유소에서 기름을 넣을 수 있다. 

'주어진' 상황에서 어떤 주유소를 선택해야 최소한으로 주유소를 선택하며 도착지까지 갈 수 있을까?

 

 

4. 문제 풀이

 

이 문제는 우선순위 큐 2개를 써야 한다.

첫 번째로 주어진 주유소가 순서대로 주어진다는 보장이 없기 때문이다.

 

두 번째로 현재 내가 갈 수 있었던 주유소 중 기름을 가장 많이 넣을 수 있는 주유소를 선택하기 위함이다.

 

 

다음의 아이디어만 가지고 문제를 해결할 수 있다.

갈 수 있는 주유소 중 기름을 가장 많이 주는 주유소를 우선적으로 선택해야만 최소 횟수를 구할 수 있다.

 

절차는 다음과 같다.

1) 나에게 기름 x L가 있다고 가정하자.

 

2) 이 기름을 모두 사용해서 현재 위치 + x km 위치에 도착했을 때, 도착점을 넘었다면 횟수 출력 후 종료.

 

3) 현재 위치 + x km 위치로 이동하면서 만난 주유소를 기름의 양을 내림차순으로 정렬하는 우선순위 큐에 모두 삽입.

 

4) 이 중에서 가장 기름을 많이 넣을 수 있는 주유소를 선택하자(우선순위 큐에서 root). 그리고 2)의 절차로 이동. 이때 주유소의 기름의 양을 x L로 가정

 

5) 갈 수 있는 주유소가 없다면 도착점까지 도달할 수 없음을 의미 -1 출력 후 종료

 

 

5. 코드

#include <cstdio>
#include <queue>
using namespace std;

struct Gas
{
	Gas() {}
	Gas(int l, int q) :location(l), quantity(q) {}
	int location;
	int quantity;

	bool operator < (const Gas& other)const
	{
		return location > other.location;
	}
};

class Comp
{
public:
	bool operator()(const Gas& lhs, const Gas& rhs)const
	{
		return lhs.quantity < rhs.quantity;
	}
};

int n, ans;
int cur, fin;

priority_queue<Gas> gasStation;
priority_queue<Gas, vector<Gas>, Comp> pq;

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
	{
		Gas item;
		scanf("%d %d", &item.location, &item.quantity);
		gasStation.push(item);
	}

	scanf("%d %d", &fin, &cur);

	while (cur < fin)
	{
		while (!gasStation.empty())
		{
			Gas item = gasStation.top();
			
			if (item.location <= cur)
			{
				gasStation.pop();
				pq.push(item);
			}
			else
				break;
		}

		if (!pq.empty())
		{
			cur += pq.top().quantity;
			pq.pop();
			++ans;
		}
		else
		{
			ans = -1;
			break;
		}
	}

	printf("%d", ans);


	return 0;
}

 

6. 결과