boj 2836 - 수상 택시

목차

개요

개요 3줄 요약

설명

코드

---

개요

이 문제는 [boj 2170 - 선 긋기]의 응용입니다. 다만 이를 어떻게 응용해야 할지 생각이 필요한 문제지요.

 

힌트는 "1) 수상택시가 N명의 모든 인원을 수용할 수 있고, 2) 0에서 출발해서 M까지는 무조건 가야 한다"입니다.

 

이를 곰곰이 생각해보면 모든 인원을 수용할 수 있으므로, 정방향 승객은 마치 일상의 버스처럼 시점에서 출발하여 승객의 출발점에 도착하면 태워주고, 승객의 목적지에 도착하면 내려주기만 하면 됩니다. 그 이후 종점에서 운행을 종료하죠. 즉, 정방향 승객은 어차피 수상 택시가 가는길이므로 고려할 필요가 없습니다.

 

이제 역방향을 생각해봐야 합니다. 10 → 5로 가는 승객의 경우 어떻게 하면 좋을까요? 일단 불가피하게 10에 도착한 후 태워서 5에서 내려줘야 합니다. 그리고 5 → 10까지 다시 운전해야 하죠. 결과적으로, 역방향 승객이 있으면 역행 거리 * 2 만큼 비용이 증가합니다.

 

마지막으로 역방향 승객이 여러 명일 때, 어떻게 태우고 내려야 할까요? 이는 두 가지로 나눌 수 있습니다.

1) 역행 구간이 겹치는 경우 (10 → 5 가는 승객 A, 그리고 7 → 3 가는 승객 B)

2) 역행 구간이 겹치지 않는 경우 (10 → 5 가는 승객A, 그리고 20 → 15 가는 승객 B)

 

1의 경우, 승객 A와 승객 B를 따로 태우는 것 보다 10까지 간 뒤에 A 태우고, 7에서 B 태우고, 5에서 A 내려주고, B에서 3 내려주는게 더 좋습니다. 전자의 경우는 7 → 3, 3 → 7, 10 → 5, 5 → 10 (역행 비용 18), 후자의 경우는 10 → 3, 3 → 10 (역행 비용 14) 가 됩니다.

 

2의 경우, 승객 A와 승객 B는 따로 태우는게 좋습니다. 굳이 동시에 태우자고 20 → 5, 5→20 (역행 비용 30) 처럼 움직이는 것 보다, 10 → 5, 5 → 10 , 20 → 15, 15 → 20 (역행 비용 20) 을 따로 해주는게 더 비용이 적기 때문이죠.

결과적으로, 역방향 승객들은 [boj 2170 - 선 긋기] 로 처리해주면 됩니다. 이 역행 거리에 기존 정방향 거리를 더하면 정답이 되죠.

---

개요 3줄 요약

1) 정방향 승객은 고려하지 않는다.

2) 역방향 승객은 [boj 2170 - 선 긋기] 문제 처럼 비용을 구한다. 이 비용의 2배는 역방향 승객을 위한 비용(거리)이 된다.

3) 역방향 승객을 위한 비용(거리)과 시점 ~ 종점의 거리를 더한다.

---

설명

boj 2836의 2번째 예제를 예시로 들어보겠습니다.

8 15
1 12
3 1
3 9
4 2
7 13
12 11
14 11
14 13

위 예제를 수직선에 그려보면 아래와 같습니다. 문제 조건상 수상 택시는 0에서 M까지 가야 합니다. 이는 하늘색 화살표로 표현했습니다.

어떻게 보면 정방향도 선 긋기 문제인데, 어차피 수상 택시 운영 구간에 흡수되므로 고려할 필요가 없음을 알 수 있습니다. (모든 승객을 태울 수 있기 때문에)

 

역방향 승객들을 따로 태우면?

역방향 승객들을 따로 태우면 아래와 같이 검정색 박스 부분에서 중복되는 구간이 나타납니다. 즉, 3 → 1 승객을 처리하는 과정에서 3 → 2의 역방향 운행을 필요로 합니다. 근데 이 과정은 4 → 2의 손님에게도 필요한데, 별개로 태우니 중복된 비용이 발생하는 것이죠.

이 방법의 비용은 이 예제에서 33이 됩니다.

 

끝까지 가서 역방향 승객을 한 번에 처리하면?

그러면, 역방향 승객이 가장 멀리 위치하는 14까지 간 다음에 1 까지 돌아오면서 한 번에 처리하면 어떨까요? 이 방법은 아래 그림과 같습니다. 보시면 4 ~ 10은 역방향 손님과 전혀 관련이 없는데도 불구하고 수상택시를 역행해야 합니다. 따라서 낭비 구간이 발생하죠.

이 방법의 비용은 43입니다.

 

선 긋기로 처리하면?

정확하게 선 긋기로 처리하면 아마 수상 택시가 다음과 같이 운행 할 겁니다. 이 경우, 중복되는 구간도 없고 낭비되는 구간도 없이 역방향 승객들을 처리할 수 있습니다.

이 방법의 비용은 27 입니다.

---

코드

※주의할 점

1. 역방향 손님의 출발 점을 내림차순으로 정렬해야 합니다. 그래야 가장 오른쪽부터 왼쪽까지 sweeping을 하며 역행에 필요한 비용을 계산할 수 있죠.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct vec{
        int x,y;
}Vec;
bool cmp(const Vec& a, const Vec& b){
        return a.x > b.x;
}
int N, M;
Vec arr[300000];
int cnt;
int main(){
        int a,b;
        scanf("%d %d",&N,&M);
        for(int i=0;i<N;i++){
                scanf("%d %d",&a, &b);

                                //역방향 승객만 고려
                if(a>b){
                        arr[cnt].x = a;
                        arr[cnt++].y = b;
                }
        }
        sort(arr, arr+cnt, cmp);

        int start = M+1, end = M+1;
        long ans = 0;
        for(int i=0;i<cnt;i++){
                if(end > arr[i].x){ // 역방향 손님이 지금 처리중인 운행 구간과 겹치지 않는 경우
                        ans += (start-end)*2;
                        start = arr[i].x;
                }
                if(end > arr[i].y){ // 역방향 손님이 지금 처리중인 운행 구간에 겹치는 경우
                        end = arr[i].y;
                }
        }
        ans += (start-end)*2;
        printf("%ld\n",ans+M);
        return 0;
}