수상 택시( BOJ 2836 )

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

2836번: 수상 택시

 

문제 파악하기

상근이가 0번에서 M번으로 이동하면서 N명의 사람들을 목적지까지 태워주는데 필요한 최소 이동거리를 구하는 문제입니다. N명의 사람들은 항상 0번 ~ M번 사이의 위치에서 이동한다는 점에 초점을 맞추면 문제를 쉽게 해결할 수 있습니다. 상근이는 가장 오른쪽 위치인 M번으로 이동해야 하기 때문에 오른쪽으로 이동하는 사람(ex. 1 > 3으로 이동)은 신경쓸 필요 없습니다. 우리가 생각해야할 사람들은 왼쪽으로 이동하는 사람(ex. 3 > 1으로 이동)입니다.

 

문제 해결하기

왼쪽으로 이동하는 사람들이 있으면 상근이는 무조건 왼쪽으로 이동해야 합니다. 그렇기에 M번에 최소한의 이동으로 도착하기 위해서는 왼쪽으로 최소한의 거리만큼만 이동해야 합니다. 따라서, 우리는 왼쪽으로 이동하는 사람들만 모아놓은 후, 왼쪽으로 얼만큼 이동해야 하는지 확인할 필요가 있습니다.

 

A와 B의 이동 거리는 항상 3가지 경우 중 1가지에 포함됩니다.

(1) A의 이동거리(5 -> 3)가 B의 이동거리(8 -> 1)에 포함되는 경우

(2) A의 이동거리(5 -> 3)가 B의 이동거리(4 -> 1)에 겹치는 경우

(3) A의 이동거리(5 -> 3)와 B의 이동거리(2 -> 1)가 서로 겹치지 않는 경우

 

(1)번의 경우에는 B의 이동 거리가 더 크기 때문에 상근이는 B의 이동거리만큼만 이동하면 됩니다. (2)의 경우에는 A와 B 모두 태워주어야 하기에 A의 시작지점(5)부터 B의 종료지점(1)까지 이동해야 합니다. (3)의 경우에는 A와 B 각각 해당 이동거리만큼 이동하면 됩니다. 이렇게 우리는 이동거리가 서로 겹치는 사람들을 찾아서 한 번에 태워주면 가장 적게 이동할 수 있습니다.

 

그렇다면 겹치는지 아닌지 구하는 방법은 어떤 것이 있을까요? 이 때, 정렬을 사용할 수 있습니다. 우선 시작점을 기준으로 정렬한 후, 시작이 가장 뒤쪽인 사람부터 하나씩 확인하면서 현재 이동구간의 범위를 체크하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define INF 0x7FFFFFFF
#define lint long long int
#define PAIR pair<int, int>
using namespace std;
 
int N, M, a, b;
vector< PAIR > inp;
 
lint ret;
PAIR pos;
 
bool cmp(PAIR a, PAIR b) {
    if(a.second == b.second) return a.first > b.first;
    else return a.second < b.second;
}
 
int main() {
    // input
    scanf("%d %d", &N, &M);
    for(int i=0;i<N;i++) {
        scanf("%d %d", &a, &b);
 
        if(a>b) inp.push_back({b, a});
    }
 
    // sort
    sort(inp.begin(), inp.end(), cmp);
 
    // search
    ret = M;
    pos = make_pair(INF, INF);
    for(int i=inp.size() -1;i>=0;i--) {
        // 포함되는 경우
        if(pos.first <= inp[i].first and inp[i].second <= pos.second) continue;
 
        // 연결되는 경우
        else if(inp[i].first < pos.first and pos.first <= inp[i].second) pos.first = inp[i].first;
 
        // 분리된 경우
        else {
            ret += (pos.second - pos.first)*2;
            pos = inp[i];
        }
    }
 
    ret += (pos.second - pos.first)*2;
 
    // 출력
    printf("%lld", ret);
}

후기

시작과 종료지점이 정해져있어서 문제를 제대로 파악했다면 나름 쉽게 해결할 수 있는 문제입니다. 스위핑 문제라고 하면 어려워보이지만 실상은 정렬한 다음에 한번씩 값을 살펴보는 것이라 그리 어렵지 않다고 생각합니다. 정렬을 배운 사람들에게 추천하고 싶은 문제입니다.