https://www.acmicpc.net/problem/1826
문제
> 성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다.
> 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다.
> 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다.
> 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다.
> 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.
> 그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다.
> 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.
> 정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다.
> 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.접근
그리디를 사용하여 갈 수 있는 주유소 중에서 기름을 더 많이 주는 주유소를 매번 고른다. 예제를 예를들어 보면 초기에 10주어졌고 이를 통해 갈 수 있는 주유소는 (4,4)와 (5,2)이다. 이 중 (4,4)가 더 많이 주니까 이걸 고르면 총 연료는 14가된다. 그럼 14로는 (4,4), (5,2), (11,5)가 있는데 앞 두 주유소는 이미 들렀으니 (11,5)만 추가된다. 그럼 더 많이 주는 (11,5) 주유소를 선택하고 총 기름은 19가 된다. 이제 19기름으로 갈 수 있는 주유소는 모두 갈 수 있는데 앞 세 곳은 이미 갔으니 마지막 (15,10)만 추가한다. (5,2)보다 (15,10)이 더 많이 주므로 이를 선택하면 총 기름은 29가 된다. 따라서 도착할 수 있게 되고 세 곳을 가는게 최적의 답이 된다.
문제해결
> 주유소 수를 입력받고, 주유소의 거리와 주는 기름을 입력받아 저장한 뒤, 가까운 순서대로 정렬해준다.
> 도착지점까지의 거리와, 초기연료를 입력받고 주유소를 고르는 메소드인 Drive에 이를 넣어 호출한다.
>우선순위 큐를 선언하고 기름의 양으로 많은순서대로 정렬할 것이다.
> 총 기름이 도착 지점의 거리보다 커지면 갈 수 있다는 뜻이므로 커질떄 까지 반복을 돈다.
> 갈 수 있는 주유소를 탐색하기 위해 저장된 주유소 중 가진 연료보다 가까운 거리의 주유소 중 방문 안했던 주유소만 골라 큐에 넣고 방문처리 해준다.
> 만약 주유소를 다 돌아서 큐에 더 이상 남은게 없는데 총 연료가 도착지점 보다 작다면 못가므로 -1을 출력하고 끝내준다.
> 그게 아니라면 우선순위 큐의 최 상단의 기름을 현 연료에 더해 갱신해주고 들른 주유소의 누를 증가시켜준다.
> whlie문이 깨지면 총 연료가 충분하다는 뜻이므로 cnt를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, L, P;
vector<pair<int, int>> gas;
vector<bool> visited;
int cnt = 0;
void Drive(int end, int soil)
{
priority_queue<int, vector<int>, less<int>> pq;
while (soil < end)
{
for (int i = 0; i < N; i++)
{
if (gas[i].first > soil) continue;
if (visited[i]) continue;
pq.push(gas[i].second);
visited[i] = true;
}
if (pq.empty())
{
cout << -1 << '\n';
exit(0);
}
soil += pq.top();
pq.pop();
cnt++;
}
cout << cnt << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
gas.push_back({ a, b });
}
sort(gas.begin(), gas.end());
visited.assign(N, false);
cin >> L >> P;
Drive(L, P);
}
후기
처음에 최단 경로 구하듯이 현 연료로 갈 수 있는 주유소를 모두 큐에 넣고 남은 거리, 남은 연료를 계산하여 넘겨주면서 남은 연료로 갈 수 있는 가장 먼 주유소를 고르는 방식으로 했는데 시간초과가 났다. 갈 수 있는 주유소를 탐색하고 넘겨준다는 부분이 문제일것 같았는데 문제였다. 그래서 그리디에 대해 다시 알아보고 문제를 해결하는 방식을 공부했다. 실제 이동을 고려하며 해결 하는 문제가 아니고 주어진 주유소의 사정에서 연료를 많이 주는 곳으로 정렬하며 몇개를 가야, 총 연료가 최종거리 이상이 되냐를 찾는 문제였다.
