티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/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. 결과
'알고리즘 > Greedy' 카테고리의 다른 글
boj, 백준) 12018. Yonsei TOTO (C/C++) (0) | 2021.08.26 |
---|---|
boj, 백준) 2212. 센서 (C / C++) (0) | 2021.08.14 |
boj, 백준) 1911. 흙길 보수하기(C/C++) (0) | 2021.08.12 |
boj, 백준) 1781. 컵라면 ( C/C++) (0) | 2021.08.11 |
boj, 백준) 1135. 뉴스전하기 (C/C++) (0) | 2021.05.27 |