BOJ 백준 22991번 수요응답형 버스

 

BOJ 백준 22991 수요응답형 버스

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

22991번: 수요응답형 버스

 

배차 요청이 N개, 버스가 M개 주어졌을 때, 조건을 만족하면서 배차 요청에 버스를 최대 몇 대 배차 가능한지를 구하는 문제이다. 버스를 요청에 배차 가능한 조건은 다음과 같다.

 

 

 

배차의 탑승 인원 ≤ 버스의 정원 
배차의 최대 대기 가능 시간 ≥ 버스의 도착 예정 시간

 

 

 

올해 2021년 SUAPC Summer(https://icpc-sinchon.io/suapc)에 출제되었던 문제이다. 실제로 8월에 이 대회에 참가해서 이 문제를 맞닥뜨렸는데, 이분 매칭으로 해결하는 문제인 줄 알고 시도했지만 간선의 최대 개수가 (20만)^2여서 시간제한 1초 안에 절대로 이분 매칭으로 풀 수 없는 문제이다. 그래서 대강 Greedy(그리디) 알고리즘으로 해결하는 문제임을 짐작은 했지만, 이를 실제로 어떻게 풀어야 할지 당황스러워하다가 결국 풀지 못한 채 대회를 종료했던 것으로 기억한다. 대회 종료 후 문제 해설 세션 영상을 보면서 역시 이 문제는 Greedy 알고리즘으로 해결해야 한다는 걸 깨달았다. 지금 돌이켜 보니 그때 이분 매칭에 너무 집착하지 말고 차분히 깊게 고민했으면 하는 아쉬움이 남는다.

 

사실 개인적으로 아직도 Greedy 알고리즘이 가장 어려운 것 같다. PS 실력이 부족한 나로서는 실제로 풀이 시간이 넉넉치 않은 대회에서 어떠한 문제를 Greedy 알고리즘으로 풀어야 함을 증명하는 건 너무나도 힘든 일이다. 그래서 어떠한 문제를 어떤 알고리즘을 사용해서 풀어야 하는지, 만일 해당 문제를 Greedy 알고리즘으로 해결해야 한다면 어떤 아이디어로 풀어야 하는지 직관적으로 떠올려서 전략을 짤 줄 알아야 하는데, 아직 이 정도의 실력까지 도달하기에는 스스로 역부족이라고 느낀다. 더 열심히 공부해야지. 👍

 

 

 

서론이 길었지만, 결국 개인적으로 이번 2021년 SUAPC Summer 대회와 이 문제를 통해 깨달은 건 Greedy 알고리즘을 사용할 땐 가능한 문제를 naive하게 생각한다는 것이다. 이 문제의 접근 방법을 naive하게 생각해 보자.

 

 

 

조건을 만족하면서

버스 정원이 탑승 인원에 가능한 가깝게
도착 예정시간이 최대 대기 가능 시간에 가능한 가깝게

버스를 배치하면 이득이다.

 

 

 

"왜?"라고 물어보면... 솔직히 해설 세션을 다시 봐도 내 머리로는 엄밀하게 이유를 설명할 수 없을 것 같다. 😂 정확한 증명은 여기(https://archive.suapc.kr/2021s/solution/)를 참고하면 된다. 오히려 이런 문제는 직관적으로 생각해 보는 게 더 이해하기 쉽다고 생각된다. 앞에서 탑승 인원보다 너무 큰 정원의 버스를 배차해 버리면 뒤에서 더 큰 탑승 인원이 요청으로 주어졌을 때 배차 조건을 만족할 수 있는 버스가 부족할 수 있다. 앞에서 이미 큰 정원의 버스를 배차해 버렸기 때문이다. 도착 예정시간도 정원과 마찬가지로 생각할 수 있다. 단순한 말장난처럼 보이지만, 사실 중급 난이도의 Greedy 알고리즘 문제는 이러한 아이디어를 사용하는 경우가 꽤 있다. 풀이 방법이 유사한 문제들은 여기를 참고해 보면 좋다.

 

 

 

[유사 문제]

solved.ac 

목록: https://solved.ac/search?query=tag%3Agreedy%26tag%3Atree_set 

 

BOJ 백준 19580번 마스크가 필요해

문제: https://www.acmicpc.net/problem/19580

19580번: 마스크가 필요해

 

 

 

아이디어를 찾았으면 이제 이를 어떻게 구현해야 하는가가 관건이다. 임의의 한 버스 X를 골라서 이 버스에 배차 가능한 배차 요청을 모두 리스트 L에 넣었다고 가정해 보자. 위의 정리한 아이디어에서 도착 예정 시간과 최대 대기 가능 시간을 가능한 비슷하게 배차하는 게 결과적으로 이득이라고 했다. 따라서 리스트 L에서 도착 예정 시간 이상이지만 이 값과 가장 가까운 최대 대기 가능 시간을 지닌 요청 A를 찾는다. 그러면 버스 X는 배차 요청 A에 배차하는 것이 가장 효율적이다.

 

그러나 시간 제한으로 인해 매번 모든 버스에 관해 가능한 모든 배차 요청을 리스트에 넣는 걸 반복할 수 없다. 여기서는 정렬에 관한 아이디어를 고려해 보자. 버스 X를 배차 요청 A에 배차한 상태에서 바로 다음에 볼 버스 Y의 정원이 버스 X의 정원보다 크거나 같으면, 리스트 L에 있는 모든 요청의 탑승 인원은 반드시 버스 Y의 정원보다 적거나 같을 것이다. 즉, 배차 인원만을 고려하면 리스트 L에 있는 요청은 버스 Y에도 매칭 가능한 후보라고 볼 수 있다. 그러므로 버스와 배치 요청을 각각 정원과 탑승 인원 수의 오름차순으로 정렬한 상태에서 차례대로 살펴보면 매 버스마다 모든 배차 요청을 보면서 가능한 배차 요청 리스트를 찾을 필요가 없다. 이미 리스트 L에는 배차 가능한 요청 후보가 있으므로 앞으로 가능한 배차 요청 후보만 리스트에 하나씩 넣어주면 linear한 시간 안에 구현 가능하다.

그런데 리스트 L에서 요청 A를 구할 때는 탑승 인원뿐만이 아니라 최대 대기 가능 시간도 고려해줘야 한다. 여기서부터는 문제 해결이 가능한 적합한 자료구조를 찾아야 한다. 리스트 L에 들어올 수 있는 요청의 최대 수가 20만이므로 일일이 원소 하나씩 보며 찾을 수는 없다. 그래서 이진 탐색으로 빠르게 조건을 만족하는 원소를 찾을 수 있는 자료구조를 사용한다. 여기에는 map, set, multiset 등이 있는데, 필자는 map을 사용했다. 배차 요청을 최대 대기 가능 시간의 오름차순으로 정렬했을 때, 버스의 도착 예정 시간 이상이면서 가장 첫 번째로 오는 최대 대기 가능 시간을 지닌 원소를 찾아야 한다. 이는 map의 lower_bound 함수로 구현 가능하다.

 

 

 

이를 정리하면 다음과 같다.

 

1. 버스와 배차 요청을 각각 정원, 탑승 인원 수의 오름차순으로 정렬한다.
2. 버스를 한 대씩 보면서
   
   1. 버스 정원 이하인 탑승 인원의 배차 요청을 map의 원소로 추가한다.
   2. map에서 도착 예정 시간 이상이면서 이에 가장 가까운 최대 대기 가능 시간을 지닌 배차 요청을 선택한다.
   3. 선택한 배차 요청에 현재 보고 있는 버스를 배차한다.

 

 

 

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
using pp = pair<int, int>;

int n, m, ans;
vector<pp> request, bus;

map<int, int> candidate;

int main(){
    scanf("%d %d", &n, &m);
    request.resize(n);
    bus.resize(m);
    
    for (int i = 0; i < n; i++){
        scanf("%d %d", &request[i].first, &request[i].second);
    }
    
    for (int i = 0; i < m; i++){
        scanf("%d %d", &bus[i].first, &bus[i].second);
    }
    
    sort(request.begin(), request.end());
    sort(bus.begin(), bus.end());
    
    for (int r_idx = 0, b_idx = 0; b_idx < m; b_idx++){
        // 정원보다 탑승인원이 적거나 같은 배차요청은 map의 원소로 추가
        while(r_idx < n && bus[b_idx].first >= request[r_idx].first){
            candidate[request[r_idx].second] += 1;
            r_idx += 1;
        }
        
        // map에서 버스의 도착 예정시간 이상이면서 이 값에 가가운 최대 대기 가능시간을 지닌 배차요청 찾기
        if (candidate.size() > 0){
            auto iter = candidate.lower_bound(bus[b_idx].second);
            
            if (iter != candidate.end()){
                ans += 1;
                iter->second -= 1;
                if (iter->second == 0){
                    candidate.erase(iter->first);
                }
            }
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}