[백준] 2836 수상 택시

2836번: 수상 택시

fast io 미적용

문제 확인

 

경로를 합칠 수 있으면 길이가 단축되므로 경로들을 정렬해서 합칠 수 있는지 확인하는 스위핑 문제입니다.

 

풀이

 

출발지가 목적지보다 왼쪽, 낮은 수인 경우 M으로 가는 도중 처리할 수 있으므로 배열에 넣지 않습니다.

배열에는 목적지가 출발지보다 왼쪽에 있는 경우만 선택해서 담아 이를 목적지 기준으로 정렬합니다.

 

경로를 합칠 때 돌아갔다가 오는 길이를 줄이기 위해서는 서로 겹치는 부분이 있는 경우만 합쳐서 새 경로를 만들어 줍니다. 예를 들어 다음과 같은 경우 경로를 합치는 것이 좋습니다.

(10 2), (13 9)

• 경로를 합친 경우 : M + (13 - 2) * 2 = M + 22
• 따로 처리를 한 경우 : M + (10 - 2) * 2 + (13 - 9) * 2 = 16 + 8 = 24

 

만약 경로가 서로 이어지지 않는다면 불필요한 왕복이 생기므로 경로를 합치지 않는 것이 좋습니다.

(10 2), (13 11)

• 경로를 합친 경우 : M + (13 - 2) * 2 = M + 22
• 따로 처리를 한 경우 : M + (10 - 2) * 2 + (13 - 11) * 2 = 16 + 4 = 20

 

스위핑을 통해서 선형 시간에 최솟값을 찾을 수 있으며 left, right 변수를 두고 최소의 목적지, 최대의 출발지를 기록해두며 경로가 겹쳐 있는지 판단합니다.

int left = ary[0].목적지, right = ary[0].출발지; //목적지 < 출발지
	for (int i = 1; i < n; i++) {
		if (ary[i].목적지 < 최대 출발지(right)) { // 경로가 겹침
			right = max( ary[i].출발지, right );
		}
		else {//경로가 겹치지 않음
			res += (right - left); // 합친 경로 길이
			left = ary[i].목적지, right = ary[i].출발지;
		}
	}

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct pir {
    int cur, dest;
};
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    pir ary[300000];
    cin >> n >> m;
 
    for (int i = 0; i < n;) {
        cin >> ary[i].cur >> ary[i].dest;
        if (ary[i].cur > ary[i].dest)i++;
        else n--;
    }
 
    sort(ary, ary + n, [](const pir &a, const pir& b)->bool {
        return a.dest < b.dest;
    });
 
    long long res = 0;
    int left = ary[0].dest, right = ary[0].cur;
    for (int i = 1; i < n; i++) {
        if (ary[i].dest < right) {
            right = right < ary[i].cur ? ary[i].cur : right;
        }
        else {
            res += right - left;
            left = ary[i].dest, right = ary[i].cur;
        }
    }
    res += right - left;
    cout << (res<<1) + m;
}