[C++] 13334 - 철로 (골드2)

1. 문제 설명

 

13334번: 철로

 

---

2. 아이디어

 

[C++] 2170 - 선 긋기 (골드5)

이전과 마찬가지로 스와핑 알고리즘을 사용하는데 몇 가지 제한이 걸렸다.

 

단순히 총 길이를 체크하는 것이 아니라 그 중에서도 가장 많은 사람을 포함하는 길이를 체크해야 한다.

우선 입력을 받을 때, 애초에 길이가 d 초과인 케이스는 제거한 후 정렬을 실시한다.

 

여기서 조금 재밌는 발상을 해볼 수 있는데 현재 모든 사람의 경로는 시작점을 기준으로 정렬되어 있다.

그런데 정렬을 할 때, 시작점이 아니라 끝점을 기준으로 생각해볼 수 있다.

예외 처리 단꼐에서 d의 길이를 벗어나는 케이스는 모두 제거했으니 남은 경우는 모두 second -d <= first이다.

즉 배열에서 first를 지날 때는 cnt를 1만큼 제거하고,

second - d 지점을 지날 때는 아직 자가 해당 구간을 포함하고 있음을 의미하므로 cnt를 1 증가시킨다.

 

이런 식으로 배열을 순회하면서 최댓값을 갱신하면 정답을 구할 수 있는 재밌는 문제였다!!

 

---

3. 코드

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

#define INF 1e9

using namespace std;
typedef pair<int, int> p;

int n, d;
vector<p> dist, tmp;

void input_value() {
    cin >> n;

    for (int i=0; i<n; i++) {
        int h, o; cin >> h >> o;
        if (h > o) { swap(h, o); } // 무조건 작은 값을 first
        dist.push_back({h, o});
    }
    cin >> d;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input_value();

    for (auto i : dist) { 
        if (i.second - i.first > d) continue; // 애초에 길이 오버인 애들 정리
        tmp.push_back({i.first, 1});
        tmp.push_back({i.second-d, -1}); // d를 평행이동 하다가 범위를 벗어나면 cnt에서 제외
    }
    sort(tmp.begin(), tmp.end());

    int cnt = 0, ans = 0;
    for (auto i : tmp) {
        cnt -= i.second; // second - first <= d라면 second - d <= first가 성립한다.. 즉, cnt기준을 first가 아니라 second로 잡는다.
        ans = max(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}