백준 2836 : 수상 택시 (C++)

본문 링크

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

using namespace std;

int main()
{
    int N , M;

    cin >> N >> M;

    vector<pair<long long, long long>> V;

    for (int i = 0 ; i < N ; i ++)
    {
        long long A,B;
        cin >> A >> B;

        if (A>B)
        {
            V.push_back(make_pair(B,A));
        }
    }

    sort(V.begin() , V.end());

    long long left=V[0].first; 
    long long right=V[0].second;
    long long total = 0;

    for (int i = 1 ; i < V.size() ; i ++)  
    {
        if (right<V[i].first) // 구간을 벗어난다면
        {
            total+=right-left;
            right=V[i].second;
            left=V[i].first;
        }

        right=max(right , V[i].second);
    }

    total+=right-left;

    cout << M+total*2;
}

📌 어떻게 접근할 것인가?

스위핑을 통해 풀었습니다.

문제에서 원하는 것은 $0$ 부터 $M$ 으로 이동할때 , $A$ 에 위치하는 사람이 $B$ 로 이동을 원해서 모두 옮겨주고 $M$ 으로 도착하는 최단경로를 구하는 문제입니다.

가만히 생각해보면 $A<=B$ 일때는 신경을 안써도 됩니다. 보트에는 최대 $N$ 명이 전부 탈 수 있기 때문에 그냥 가는 길에 보트에 합류해서 도착점으로 가는동안 매번 목적지에 데려다 주면 되기 때문입니다.

그래서 생각해야할 부분은 $A>B$ 일 때 입니다.

즉 왔던길을 다시 되돌아 가야하는경우 인데 , 이 부분도 생각해봅시다.

$A$ 에서 $B$ 지점에 가고 다시 $A$ 로 이동하는데는 얼마의 이동이 필요할까요?

바로 $2*(A-B)$ 입니다. 즉 왔다 갔다해서 2배 입니다.

따라서 저는 $A>B$ 의 좌표를 입력받을때 , $(B,A)$ 와 같이 값을 넣어주었고

이제 그것에 대한 스위핑을 해서 값을 구했습니다.

따라서 결론은 가고자 하는 총 거리 $M$ , 그리고 $A>B$ 일때의 스위핑의 합의 두배.

이 두값의 합이 정답이 됩니다.

✅ 코드에서 주의해야할점

int 사용지 오버플로우가 발생할 수 있으므로 long long 을 써줘야 합니다.