본문 바로가기

알고리즘 관련/BOJ

BOJ)1826 연료 채우기

문제:icpc.me/1826


1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다.


우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue<int> pq;
int n, l, p, it, r;
pair<intint> a[10002];
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++)
        scanf("%d%d"&a[i].first, &a[i].second);
    scanf("%d%d"&l, &p);
    sort(a, a + n);
    while (p < l) {
        while (a[it].first <= p) {
            if (it == n)break;
            pq.push(a[it].second);
            it++;
        }
        if (!pq.size())break;
        r++;
        p += pq.top();
        pq.pop();
    }
    printf("%d\n", p < l ? -1 : r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3770 대한민국  (0) 2017.04.06
BOJ)6091 핑크 플로이드  (0) 2017.04.06
BOJ)2056 작업  (0) 2017.04.06
BOJ)7579 앱  (0) 2017.04.05
BOJ)2157 여행  (0) 2017.04.05