[BOJ] 13334번 - 철로

백준 13334번 - 철로

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	3652	1374	903	38.590%

문제

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.

출력

출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.

---

예제 입력 1

8
5 40
35 25
10 20
10 25
30 50
50 60
30 25
80 100
30

예제 출력 1

4

예제 입력 2

4
20 80
70 30
35 65
40 60
10

예제 출력 2

0

출처

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

13334번: 철로

알고리즘 분류

• 자료구조
• 정렬 
• 스위핑
• 우선순위 큐

접근 방법1( Line Sweeping & Priority Queue) 

문제를 보다 더 구체화 하기 위하여, 문제에서 원하는 정답이 무엇인지 수식화 해보자.

${f\left( x\right) =\left[ a_{i},b_{i}\right] \subseteq \left[ x,x+d\right] }$ ${\text{(단,}a_i \leq b_i)}$ 를 만족하는 i의 개수일 것이다.

우리가 원하는 정답은 ${f_{max}}$ 를 찾는 것이다.

 

문제의 정의상 x가 될 수 있는 범위는 (${-10^9 }$ ~ ${10^9}$) 이지만, f(x)의 값이 변하는 지점만 집중해보자.

f(x)가 변할 수 있는 구간은 ${a_1, a_2, a_3, ..., a_n}$ 까지 일 것이다.

즉, 주어진 집<->사무실 좌표 값이 주어진 곳에서 f(x)의 값이 변할 가능성이 있다는 뜻이다.

그렇다면, 최대 ${10^6}$개의 범위로 x가 제한되게 된다.

 

가능한 x의 범위에 맞춰서 탐색을 진행해보자. 단, 이 때 선형적으로 모든 선들에 대하여 탐색을 하는 행위는 TLE일 것이므로 해가 될 수 없는 값들을 필터링해보자. 

 

선형적으로 탐색할 수가 없다면, 어떠한 특성을 유지시키므로서 이전의 원소를 두번 다시 살펴보지 않고 이 후 탐색에서도 해가 절대 되지 못하는 경우를 제거하는 테크닉을 많이 사용한다. 

 

 

먼저, ${(h_i, o_i)}$ (단, ${h_i \leq o_i}$) 를 ${o_i}$를 기준으로 정렬해주자.

우리는 ${o_i}$를 기준으로 하여 다음과 같이 임의의 선분을 잡을 예정이다.

그 이유는 ${o_i}$를 기준으로 오름차순 정렬을 수행하게 될 경우 ${[h_{i}, o_{i}]}$에 있는 직선은 

${[h_{i+1}, o_{i+1}]}$ 에 있는 직선보다 좌표 상 왼쪽에 위치한다는 규칙을 유지할 수 있기 때문이다.

 

존재하는 모든 경우를 고려해주기 위해 길이d인 임의의 선분을 ${[o_i - d, o_i]}$ 로 잡아준다.

이 구간에 포함되는 모든 직선들을 구해주기 위해 이전까지 탐색한 직선들 중 가장 작은 값부터

직선에 포함되지 않는 점들을 pop해준다. 직선에 완전포함되지 않는 경우는 ${\{a_i, b_i\}}$에 대해

${a_i < o_i - d}$ 일 경우이다. 

이를 구현하기 좋은 자료구조는 min heap 이다.

또한, 이전에 heap에서 제거된 원소는 이후 선분에서도 겹칠 수가 없으므로, heap에 들어가는 원소의 수는 for문이 돌아가는 동안 

total = N 인 것을 유추할 수 있다.

 

이렇게 가능한 모든 정의역 x에 대해 탐색을 수행한다면, O(NlogN) 시간에 정답을 구할 수 있다.

 

소스 코드1

#define FASTIO cin.tie(0)->sync_with_stdio(false), cout.tie(0)
#define FILEMODE freopen("input.txt","r",stdin), freopen("output.txt","w",stdout)
//////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

int n, d;
vector<pair<int,int>> v;
int main(void){
#ifndef ONLINE_JUDGE
    FILEMODE;
#endif
    FASTIO;
//////////////////////////////////////////////////////////////////
    cin >> n;
    v.resize(n);

    // pq 에는 항상 현재 선분에 포함되어 있는 원소들을 유지한다.
    // 또한 PQ에는 동일한 원소가 다시 들어가지 않는다.
    // 그렇게 될 경우, 조금의 adjusing 을 통하여 nlogn 복잡도로 구현가능하다.

    for(int i=0; i<n; i++){
        cin >> v[i].first >> v[i].second;
        if( v[i].first > v[i].second )
            swap(v[i].first, v[i].second);
    }

    cin >> d;
    int ans = 0;
    sort(v.begin(), v.end(), [](const auto& a, const auto& b)->bool {
       if( a.second == b.second )
           return a.first < b.first;
       return a.second < b.second;
    });

    priority_queue<int,vector<int>,greater<>> PQ;
    for(int i=0; i<n; i++){
        if( v[i].second - v[i].first > d ) continue;
        PQ.push(v[i].first);
        // 현재 라인은 [v[i].second-d, v[i].second]
        while(!PQ.empty() && PQ.top() < v[i].second - d) PQ.pop();
        ans = max<int>(ans, PQ.size());
    }

    cout << ans ;

    return 0;
}

접근 방법2(집합의 관점) 

위에서 설명했다시피 우리가 구하고자 하는 것은

${f\left( x\right) =\left[ a_{i},b_{i}\right] \subseteq \left[ x,x+d\right] }$ ${\text{(단,}a_i \leq b_i)}$ 를 만족하는 i의 개수

에 대하여 ${f_{max}}$를 찾는 것이다.

 

f(x)가 범위이므로, ${\{[a_i, b_i]\}}$ 각각에 대한 집합을 다음과 같이 표현할 수 있다.${\begin{aligned}A=\left\{  i| a_{i}\geq x\right\} \\B=\left\{  i| bi\leq x+d\right\} \end{aligned}}$

 

그렇다면 우리가 구하고자하는 ${f\left( x\right) =A\cap B}$ 의 꼴을 가진다.

이를 좀 더 분해해보면 다음과 같은 형태가 된다.

${f\left( x\right) =n\left( A\right) +n\left( B\right) -n\left( A\cup B\right)}$

${n\left( A\cup B\right)}$를 좀 더 분해해보면, 다음과 같은 수식을 볼 수 있다.

 

${n\left( A\cup B\right) =U-n\left( \left( A\cup B\right) ^{c}\right) =U-n\left( A^{c}\cap B^{c}\right) }$

 

또한, 다음을 만족한다.

만약, 우리가 전체 집합에 ${\left( A^{c}\cap B^{c}\right)}$에 해당하는 원소를 넣지 않는다면 이를 공집합으로 유지시킬 수 있다.

n(A) 와 n(B)는 ${a_i, b_i}$를 독립적으로 보고 각각을 정렬 후 parametric search했을 때 해당 조건을 만족하는 원소의 개수가 되겠고

전체집합은 ${\{a_i, b_i\}}$의 개수이므로, 해당 되는 원소의 개수를 적절히 카운팅한다면 우리가 원하는 정답을 얻을 수 있다.

 

스크롤의 귀찮음을 막기위해.. A, B 집합을 아래에 적어두었다.

${\begin{aligned}A=\left\{  i| a_{i}\geq x\right\} \\B=\left\{  i| bi\leq x+d\right\} \end{aligned}}$

 

소스 코드2

#define FASTIO cin.tie(0)->sync_with_stdio(false), cout.tie(0)
#define FILEMODE freopen("input.txt","r",stdin), freopen("output.txt","w",stdout)
//////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;


int N, D;
vector<pair<int,int>> v;
vector<int> a,b;

int main(void){
#ifndef ONLINE_JUDGE
    FILEMODE;
#endif
    FASTIO;
//////////////////////////////////////////////////////////////////
    cin >> N ;
    v.resize(N);
    for(int i=0; i<N; i++){
        cin >> v[i].first >> v[i].second;
        if( v[i].first > v[i].second )
            swap(v[i].first, v[i].second);
    }
    cin >> D;

    for(int i=0; i<N; i++){
        if( v[i].second - v[i].first > D )
            continue;
        a.push_back(v[i].first);
        b.push_back(v[i].second);
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int current = -1, ans = 0;
    for(int i=0; i<a.size(); i++){
        if( a[i] == current ) continue;
        current = a[i];

        int temp = a.end() - lower_bound(a.begin(), a.end(), current);
        temp += upper_bound(b.begin(), b.end(), current+D) - b.begin();
        temp -= a.size();
        ans = max(ans, temp);
    }
    cout << ans ;

    return 0;
}