백준, BOJ, 1826번, 연료 채우기C++ [CPP] ★★★★★

이것은 그냥 생각했을 때.. 단순한 문제지만

시간을 단축하려면 조금 더 머리가 필요한 문제였다.

중요한 문제라고 생각한다.

우선순위 큐라면 이 문제가 가장 대표적이라고 생각한다.

나는 시간초과나서 실패했다.

그리고 다시 답을 찾게되었다.

https://www.acmicpc.net/problem/1826

 

---

 

#시간 초과 풀이

#include <bits/stdc++.h>

using namespace std;




//해당 위치의 값이 0이 아니면 주유소의 위치이며 값은 기름의 양임
int stations[1000001];

//이렇게 하면.. 시간 초과남, 답은 나올지 모르겠으나 풀이는 아님

int N;
int ans = 123456789;

int l,p; //도착위치, 초기 기름양

void func(int pos, int cnt, int fuel){
    if(fuel == 0)return;
    if(pos >= l){
        ans = min(ans, cnt);
        return;
    }
    func(pos+1, cnt, fuel-1);
    if(stations[pos+1] > 0)func(pos+1, cnt+1, fuel + stations[pos+1] - 1);
}

int main(){
    cin >> N;
    
    for(int i = 0; i<N; i++){
        int a,b;
        cin >> a >> b;
        stations[a] = b;
    }
    cin >> l >> p;
    
    func(0,0,p);
    cout << ans << '\n';
    
    
    
    
    return 0;
}

 

 

#맞은 풀이 => 주석을 잘보자

#include <bits/stdc++.h>

using namespace std;

//가장 적은 수의 주유소를 들리면서 끝까지 가야한다..?
//어떤 주유소를 들리든 마을을 가는 길이므로 주유소에 들리는 비용은 같다.
//다만 주유소에 들려서 얻는 기름의 양이 다르다.
//0 ~  x  ~ y ~ finish 라고 해보자

//x까지 오는 데 기름을 다써버렸다.
//그렇다면 x는 finish가 아니므로 x 나 이전에 만났던 주유소들을 들렸어야 함이 분명하다.
//그렇게 되면 가장 기름의 양이 많은 것을 선택해서 어찌저찌 y까지 왔다.
//y도 역시 finish가 아니므로 이전의 주유소 중에서 기름의 양이 가장 많은 것을 선택해야 한다.
//그래도 도착 못한다? 계속 주유소를 들리면 된다.
//결국 도착하게 된다.

//위 설명이 가장 정확하게 설명한 것 같다. 나머지는 그냥 풀이만 써놨지.. 이해가 어렵게 써놓았다.
//즉, 현재의 위치를 기준으로 이전에 어떤 주유소를 들렸어야 했는가? 를 생각하자는 것이다.


//주유소 개수가 많아 위치마다 가장 연료양이 많은 주유소를 계속 찾기는 힘들다.
//때문에 정렬이나 우선순위 큐같은 것을 이용해야 한다.

int N;
bool impossible = false;

int main(){
    cin >> N;
    deque<pair<int,int>> stations;   // {position, fuel}
    for(int i = 0; i<N; i++){
        int a,b;
        cin >> a >> b;
        stations.push_back({a,b});
    }
    
    int l,p;
    cin >> l >> p;
    
    //가까운 순으로 정렬 =>
    sort(stations.begin(), stations.end());
    
    
    //중요한 사실 priority queue의 top 원소는 container의 back 에 있는 원소이다.
    //비교 연산을 위함 => bool operator를 오버라이딩
    struct compare{
        bool operator()(pair<int,int> a, pair<int,int> b){
            return a.second < b.second;  //fuel이 많은 것이 true 뒤로
        }
    };
    
    //가장 연료가 많은 주유소를 꺼내기 위한 우선순위 큐
    priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq; // compare를 만들어야함,
    
    int pos = p; //현재 연료로 갈 수 있는 최대 거리
    int cnt = 0;
    while(1){
        if(pos >= l)break;
        //도달하지 못했다면 pos 이전의 주유소 중 가장 연료가 많은 주유소를 들린다.
        //주유소를 꺼냄
        while(!stations.empty()){
            auto cur = stations.front();
            if(cur.first > pos)break; //그 뒤의 주유소는 집어넣지 않음.
            stations.pop_front();
            pq.push(cur);
        }
        //꺼낼 주유소가 없으면 도달하지 못하는 것임.
        if(pq.empty()){
            impossible = true;
            break;
        }

        
        //우선순위 큐에서 꺼낸게 가장 큰 주유소
        cnt++;
        //cout << pq.top().first << '\n';
        int temp = pq.top().second; pq.pop();
        pos += temp;
        
    }
    if(impossible)cout << -1 <<'\n';
    else cout << cnt << '\n';
    
    return 0;
}