[BOJ] 백준 22991 - 수요응답형 버스 (SUAPC 2021 Summer)

문제 링크

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

22991번: 수요응답형 버스

 

풀이

버스의 최대 배정

배차 요청에 탑승 인원, 대기 가능시간이, 버스에 정원과 도착 예정 시간이 있습니다.

어떤 배차 요청에 버스가 배정되려면 (탑승 인원 $\leq$ 버스 정원), (대기 가능 시간 $\geq$ 도착 예정 시간)을 만족해야 합니다.

 

인원을 $x$축으로, 시간을 $y$축으로 두고 그래프를 그려봅시다.

검은 점은 배차 요청을, 빨간 x는 버스를 나타냅니다.

 

 

 

대충 보시면 알겠죠..? 가장 많은 버스를 배정하려면 각 요청 우하단의 버스 중, 가장 가까운 버스를 배정해주어야 합니다.

 

어떻게..?

1) 버스가 요청의 오른쪽 구간에 있어야 함

문제를 좀 간단히 만들어서, 시간 축이 존재하지 않는 일차원 수직선이라고 생각해봅시다.

이런 문제는 많이 풀어보셨잖아요. lower bound를 이용해서 가장 가까운 버스를 $O(logM)$만에 찾을 수 있습니다.

 

2) 버스가 요청의 아래쪽 구간에 있어야 함

배차 요청마다 칠해둔 직사각형을 잘 봅시다. 전부 바닥이 축과 닿아있죠? 

이는 어떤 요청을 처리할 때, 그보다 아래 범위의 모든 버스에 대해 마치 y축이 없는 것처럼 lower bound를 이용할 수 있다는 말이 됩니다.

 

위 두 항목을 합쳐봅시다.

요청과 버스를 모두 (시간, 인원) 순으로 정렬합니다.

시간이 낮은 순서로 요청을 처리하면, 시간이 높아질 때마다 아래 범위에 있는 버스들을 계속 누적해갈 수 있기 때문에 2번 항목을 $O(M)$의 복잡도로 처리할 수 있게 됩니다. 그렇게 누적된 버스 사이에서 lower bound로 배정될 버스를 선택할 수 있습니다.

 

map을 이용하자

사실 lower bound에는 함정이 있습니다. 배열에서 lower bound를 이용하려면 그 배열이 정렬되어있어야 합니다.

y축을 따라 버스를 누적하면서 매번 정렬하게 되면 결국 $O(M^2logM)$이 되어 의미가 없습니다. 거기다 이미 배정된 버스를 제거해야 하는데 얘도 시간복잡도가 큽니다.

 

map은 삽입, 삭제, 조회가 $O(logN)$인데 심지어 정렬까지 해주고, 자체 lower_bound도 있습니다. 치트키 자료구조..

y값인 시간은 탐색의 순서를 강제하면서 이미 고려가 되었으니 x값인 인원과 그 개수만 map에 넣어가며 관리해주면 1번 항목을 쉽게 처리할 수 있습니다.

 

자세한 구현은 코드를 참고해주세요.

 

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;

int n, m;
map<int, int> busMap;
vpii req, bus;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int num, t;
        cin >> num >> t;
        req.emplace_back(t, num);
    }
    for (int i = 0; i < m; i++) {
        int num, t;
        cin >> num >> t;
        bus.emplace_back(t, num);
    }
    sort(all(req));
    sort(all(bus));

    int ans = 0, busIdx = 0;
    for (auto &now: req) {
        auto[y, x] = now;
        while (busIdx < m && bus[busIdx].ft <= y) {
            busMap[bus[busIdx++].sd]++;
        }
        auto b = busMap.lower_bound(x);
        if (b != busMap.end()) {
            ans++;
            if (--(b->sd) == 0) {
                busMap.erase(b);
            }
        }
    }
    cout << ans;
}