BOJ 1826 : 연료 채우기

3줄요약

• 그리디

 

서론

 

이 문제는 여러모로 함정이 많은 문제이다. 대표적으로, 입력 데이터가 오름차순이더라도 문제에서 따로 명시된 정보가 없으면 정렬해야 한다는 것이다. 아이디어가 굉장히 빨리 떠올랐기 때문에, 10분만에 풀 수 있었다.

 

 

본론

 

우선 먼저 나는 냅색 문제로 접근을 시도했다. 하지만 N <= 10,000 이므로 아이디어는 폐기되었다. 이후 약간 그리디한 접근을 했고, 보다시피 맞았다. 이 문제는 다음과 같은 방법으로 풀 수 있다.

 

• 남아있는 연료의 양이 거리보다 크다면, 그냥 간다.
• 그렇지 않다면, 지금까지 지나온 주유소 중 수용량이 가장 큰 주유소를 선택하여 연료를 채우고, ans++ 한다.

 

우리는 두 번째 경우에서 직접 최댓값을 구하여 O(N^2)의 시간복잡도로 AC를 받을 수 있지만, 우선순위 큐를 이용하여 O(NlogN)의 시간복잡도로 해결할 수 있다. 코드는 밑에 있다.

 

 

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int N, alr;
pair<int, int> oil[10002];

int main() {

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &oil[i].first, &oil[i].second);
    }
    scanf("%d %d", &oil[N + 1].first, &alr); oil[0] = { 0, 0 };

    sort(oil, oil + N + 2);

    int ans = 0;
    priority_queue<int> pq; int remain = alr;
    for (int i = 0; i <= N; i++) {

        int nxt = oil[i + 1].first;
        int quantity = oil[i].second;
        int now = oil[i].first;

        pq.push(quantity);
        while (remain < nxt - now) {
            if (pq.empty()) { printf("-1"); return 0; }
            ans++; remain += pq.top(); pq.pop();
        }
        remain -= nxt - now;
    }

    printf("%d", ans);
}

 

결론

 

이 문제는 그리디 연습용으로 사용했다.

 

난이도(개인적): Gold IV

난이도(객관적): Gold III

 

Contact: How2Contact (tistory.com)