[백준(BOJ)] 철로(13334번)_C++

딱봐도 좌표를 하나씩 증가시키면서 확인하면 시간초과가 날 것 같다.

그러면 각각의 사람에 대해서 검사해야겠지?

사람을 좌표화 시켜보자.

문제에서 주어지는 h와 o의 구분은 할 필요없다. 그냥 둘 중에 더 작은 놈을 먼저 저장하는 것이 더 의미있다.

각각의 사람에 대한 정보를 입력받으면 정렬하는 것이 굉장히 중요하다.

h를 기준으로 하든 o를 기준으로 하든 상관없다. 둘 중에 하나로 정해서 정렬해보도록 하자.

나는 o를 기준으로 정렬했다.

 

o를 기준으로 정렬했으면 이제 한 사람씩 검사하는 것이다.

첫번째 사람부터 검사해보자.

d를 어떻게 놓아야 하느냐. o를 기준으로 했으므로 철로의 오른쪽 끝을 첫번째 사람의 o에 맞추고, 왼쪽은 o - d를 하면 딱 길이 d의 철로가 만들어질 것이다.

 

그러면 h가 왼쪽인 o - d 보다 크면 h와 o모두 철로에 포함되므로 해당 사람을 큐에 넣는다. 그런데 큐에 넣을 때는 h를 넣어야 한다. 각 사람을 검사할 때마다 철로의 위치가 변하는데 h가 작은 값이므로 h만 포함돼도 변한 철로에도 포함된다.

 

이렇게 각 사람을 검사하면서 철로의 위치가 변하는데 그 때마다 철로에서 벗어난 사람들을 큐에서 빼주면 된다.

이 때 큐는 우선순위큐로 작은 값이 top에 오도록 했다. 철로의 위치는 점점 오른쪽으로 이동하므로 가장 왼쪽에 있는 사람부터 탐색해주는 것이 최소한의 탐색횟수이다.

 

그럼 매번 검사할 때마다 큐의 사이즈는 철로에 포함되는 사람의 수이므로 최대 큐 사이즈를 구하면 정답이다.

 

 

---

정답

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, d, answer;
vector<pair<int, int>> v;

bool compare(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

struct cmp{
    bool operator()(int a, int b){
        return a > b;
    }
};

void sol(){
    priority_queue<int, vector<int>, cmp> q;
    
    for(int i = 0; i < n; i++){
        int left = v[i].second - d;
        int right = v[i].second;

        if (v[i].first >= left)
            q.push(v[i].first);
        
        while(!q.empty() && q.top() < left)
            q.pop();
        
        answer = max(answer, (int)q.size());
    }
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> n;
    for(int i = 0; i < n; i++){
        int h, o;
        cin >> h >> o;
        if (h > o)
            swap(h, o);
        v.push_back({h, o});
    }
    cin >> d;

    //sort
    sort(v.begin(), v.end(), compare);

    //solve
    sol();

    //output
    cout << answer;
}