boj 1826 연료 채우기

www.acmicpc.net/problem/1826

1826번: 연료 채우기

1km를 가는데 연료가 1L씩 소모됩니다.

목적지까지 가는 길에 주유소가 있어서 부족한 연료를 채우고 가야합니다.

마을에 도착했을 때, 주유소를 방문한 최소 횟수를 출력하는 문제입니다. 만약 목적지에 도착하지 못하면 -1을 출력합니다.

 

저는 거리 1당 1L이므로 연료소모를 하지않고 계속 쌓으면서 목적지까지 갈 수 있는지 확인하였고, 방법은 그리디로 하였습니다.

우선 입력으로 주어지는 주유소의 정보를 거리기준으로 오름차순 정렬합니다.

그 다음 현재 연료로 갈 수 있는 지점까지 큐에 넣어주면서 이동하다가

연료보다 더 멀리있는 주유소가 나오면 지금까지 큐에 넣어두었던 연료 중 가장 높은 값을 저장합니다.

물론 이를 위해 우선순위 큐를 사용합니다.

 

이 연산을 반복하여 마지막 목적지를 기준으로 연료가 충분한지도 확인해야합니다.

충분하면 그대로 ans를 출력, 모든 주유소를 다 들려도 목적지에 가지 못하면 -1을 출력합니다.

 

 

[C++]

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
priority_queue<int> q;
pair<int, int> list[10001];
int N, des, now, ans;
 
void func() {
    int idx = 0;
    while (idx < N) {
        if (now >= list[idx].first) {
            q.push(list[idx].second);
        }
        else {
            if (q.empty()) break;
            now += q.top();
            q.pop();
            ans++;
            idx--;
        }
        idx++;
    }
    while (!q.empty()) {
        if (now >= des) break;
        
        now += q.top();
        q.pop();
        ans++;
    }
 
    if (now >= des) cout << ans << '\n';
    else cout << "-1\n";
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    cin >> des >> now;
    sort(list, list + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N, des, now, ans;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int idx = 0;
        while (idx < N) {
            if (now >= list[idx][0])
                q.add(-list[idx][1]);
            else {
                if (q.isEmpty())
                    break;
 
                now -= q.poll();
                ans++;
                idx--;
            }
            idx++;
        }
 
        while (!q.isEmpty()) {
            if (now >= des)
                break;
            now -= q.poll();
            ans++;
        }
 
        if (now >= des)
            System.out.println(ans);
        else
            System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        des = Integer.parseInt(st.nextToken());
        now = Integer.parseInt(st.nextToken());
 
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}