[백준/C++] 13334 철로

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

13334번: 철로

 

기본적인 흐름은 철로를 움직이면서 해당되는 경로(집-사무실)의 개수를 세는 것이다.

이때 관건이 되는 부분은 두 가지라고 생각했다.

 

1 철로를 어떻게 움직일 것인가?

한 칸씩 움직일 필요는 없다. 부담스럽기도 하고, 어떤 구간은 경로가 위치하지 않을 수도 있어 낭비되는 구간이 생긴다.

최대한 철로의 시작이나 끝부터 경로가 바로 포함되도록 하는 게 이득이므로 경로들의 끝지점에 맞추어서 움직이기로 했다.

 

2 어떤 경로가 철로에 해당되는지는 어떻게 판단해야 하는가?

움직일 때마다 반복문을 다 돌려서 개수를 세는 방법도 있겠지만 비효율적이므로 현재 철로에 포함되어 있는 경로들의 시작지점을 기억하는 것이 중요하다. 철로는 오른쪽으로 움직이므로 한 번 경로가 포함되고 나면 끝지점은 신경쓸 필요가 없고, 벗어날 때에는 시작지점부터 벗어날 것이기 때문이다. 

 

요약하자면

 

1 철로는 경로들의 끝에 맞추어 오른쪽으로 움직인다

2 철로를 한 번 움직이면 무조건 하나 이상의 경로가 철로에 포함되게 된다

3 이때 포함되는 경로의 시작지점을 기억해 줘야 나중에 철로에서 벗어나게 할 수 있다

 

코드 구현 과정 1

routes = 모든 경로

ends = 모든 경로의 끝지점

starts = 현재 철로의 포함된 경로들의 시작지점

start, end = 철로 범위

idx = 몇 번째 경로까지 철로에 포함되었는가?

 

1 ends를 기준으로 철로를 움직인다

2 새롭게 포함되는 경로들의 시작지점을 starts에 삽입한다

   가끔 철로보다 긴 경로들이 있으므로 무작정 삽입하면 안 된다!

3 제외되는 경로가 있다면 starts에서 뺀다

4 개수를 갱신한다

 

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

using namespace std;

void input();
void solve();

int n, d, ans;
priority_queue<int, vector<int>, greater<int>> ends;
priority_queue<int, vector<int>, greater<int>> starts;
vector<pair<int, int>> routes;

bool cmp (pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    input();
    solve();
    
    return 0;
}

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        if (s > e)
            swap(s, e);
        routes.push_back({ s, e });
        ends.push(e);
    }
    cin >> d;
}

void solve() {
    sort(routes.begin(), routes.end(), cmp);
    int start, end = 0;
    int idx = 0;
    while (!ends.empty()) {
        if (end == ends.top()) {
            ends.pop();
            continue;
        }
        end = ends.top();
        start = end - d;
        for (; idx < n; idx++) {
            int s = routes[idx].first;
            int e = routes[idx].second;
            if (end < e)
                break;
            else if (start <= s)
                starts.push(s);
        }
        while (!starts.empty()) {
            if (start <= starts.top())
                break;
            starts.pop();
        }
        ans = max(ans, (int) starts.size());
        ends.pop();
    }
    cout << ans;
}

 

코드 구현 과정 2

사실 위의 코드는 구상과는 맞지 않는 부분이 있다. 끝지점이 같은 경로가 여러 개일 경우는 어떻게 처리할 것인지를 고민하다 보니 그런 것 같다.

그래서 while을 돌 때 끝지점이 같다면 continue를 해 주도록 한 거였는데 생각해 보니 이럴 필요가 전혀 없다는 것을 알게 되었다.

 

철로는 경로의 끝지점에 맞추어서 움직인다

= 철로는 경로의 개수만큼 움직인다

= 철로가 움직일 때마다 포함되는 경로는 1개이다

 

즉, 경로를 포함시킬 때 위의 코드처럼 굳이 반복문을 도는 것이 아니라 그냥 하나씩 추가하면 된다. 이렇게 하면 끝지점이 같은 경우도 자연스럽게 처리할 수 있게 된다.

 

그리고 하나 더 생각해 본 점이 있다면, 철로를 움직일 때 기준을 시작지점으로 잡는다면 코드의 맥락이 다음과 같이 조금 달라진다.

 

1 새롭게 포함되는 경로는 여러 개일 수 있다

2 삭제되는 경로는 한 개임이 보장된다

  시작지점이 같은 경로가 여러 개여도 마찬가지로 반복문을 돌면서 처리된다

 

상반되는 느낌이 드는 것을 알 수 있다. 기준으로서의 끝지점은 새롭게 포함되는 경로였는데, 시작지점은 다음 차례에 삭제될 경로를 의미하게 되는 것이다.

 

이 경로를 제외시키면 어떤 경로들이 포함되는가?와

이 경로를 포함시키면 어떤 경로들이 제외되는가?인 것 같다.

닭과 달걀?

 

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

using namespace std;

void input();
void solve();

int n, d, ans;
priority_queue<int, vector<int>, greater<int>> ends;
priority_queue<int, vector<int>, greater<int>> starts;
vector<pair<int, int>> routes;

bool cmp (pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    input();
    solve();
    
    return 0;
}

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        if (s > e)
            swap(s, e);
        routes.push_back({ s, e });
        ends.push(e);
    }
    cin >> d;
}

void solve() {
    sort(routes.begin(), routes.end(), cmp);
    int start, end = 0;
    int idx = 0;
    while (!ends.empty()) {
        end = ends.top();
        start = end - d;
        int s = routes[idx].first; // 새롭게 포함되는 경로!
        if (start <= s)
            starts.push(s);
        idx++; 
        while (!starts.empty()) {
            if (start <= starts.top())
                break;
            starts.pop();
        }
        ans = max(ans, (int) starts.size());
        ends.pop();
    }
    cout << ans;
}