백준 온라인 저지, 그리디 / 2836번: 수상택시 (파이썬 / 백준 골드문제)

문제

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

문제 정의

상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다.
상근이는 0번 집에 살고 있고, 보트를 이용해서 사람들을 운송하는 일을 하고 있다.
오늘은 저녁때까지 M번 집으로 가야한다. 상근이는 M번 집으로 가는 길에 사람들을 태워주려고 한다.
오늘 상근이의 수상 택시를 타려고 하는 사람은 총 N명이다. 상근이는 각 사람들이 탑승할 위치와 목적지를 알고 있다. 상근이의 보트는 매우 커서 N명 모두 보트에 태울 수 있다.
예를 들어, 사람 A가 2번 집에서 8번으로 가려고 하고, B가 6에서 4로 가려고 하는 경우를 생각해보자. 상근이는 0번 집에서 시작해서, 2번에서 A를 태우고, 6번에서 B를 태울 것이다. 그 다음 4로 돌아가 B를 내려주고, 8번에서 A를 내려다준다. 그 다음에 원래 상근이가 가려고 했던 M번 집으로 가면 된다.
상근이가 모든 사람을 데려다주고, M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (N ≤ 300,000, 3 ≤ M ≤ 109)
다음 N개 줄에는 각 사람이 상근이의 수상 택시를 타는 위치와 목적지가 주어진다. 모든 숫자는 0과 M 사이이다.

출력

첫째 줄에 상근이의 이동 거리의 최솟값을 출력한다.

예제 입력 1

2 10
2 8
6 4

예제 출력 1

14

접근 방법

- 출발지가 도착지보다 낮은 번호인 경우는 어차피 0부터 m까지 가야하기에 이를 m을 더한 뒤 그 외의 경우의 수는 합계에서 제외한다.
- 도착지를 기준으로 오름차순 정렬했을 때, 출발지가 도착지보다 높은 번호인 경우의 수만 고려하여 길이를 젠다.
- 출발지가 도착지보다 높은 번호이고 다음과 같은 경우가 동일한 직전 택시 정보와 비교했을 때, 이전 택시의 출발지가 도착지보다 높은 번호인 경우 수를 모두 고려한 뒤, 출발지가 가장 높은 곳의 번호와 도착지가 가장 낮은 곳의 번호를 고려해 길이를 계산한다.
- 단, 이전 택시의 출발지가 현재 탐색중인 택시의 도착지보다 낮은 번호라면 둘을 분리하여 거리를 계산한다.
- 따라서 다음과 같은 계산이 나온다.
- 이전 택시와 겹칠 경우 이동해야하는 거리의 최솟값 = 출발지가 가장 높은 곳의 번호와 도착지가 가장 낮은 번호와의 거리 + 도착지 가장 낮은 번호와 m까지와의 거리
- 이전택시와 겹치지 않을 경우 이동해야하는 거리의 최솟값 = 이전 택시의 출발지 - 이전 택시의 도착지 + 현재 택시의 출발지 - 이전 택시의 도착지 + 현재 택시의 출발지 - 현재 택시의 도착지

코드

# https://www.acmicpc.net/problem/2836
# 접근 방법
# 출발지가 도착지보다 낮은 번호인 경우는 어차피 0부터 m까지 가야하기에 이를 m을 더한 뒤 그 외의 경우의 수는 합계에서 제외한다.
# 도착지를 기준으로 오름차순 정렬했을 때, 출발지가 도착지보다 높은 번호인 경우의 수만 고려하여 길이를 젠다.
# 출발지가 도착지보다 높은 번호이고 다음과 같은 경우가 동일한 직전 택시 정보와 비교했을 때, 이전 택시의 출발지가 도착지보다 높은 번호인 경우 수를 모두 고려한 뒤, 출발지가 가장 높은 곳의 번호와 도착지가 가장 낮은 곳의 번호를 고려해 길이를 계산한다.
# 단, 이전 택시의 출발지가 현재 탐색중인 택시의 도착지보다 낮은 번호라면 둘을 분리하여 거리를 계산한다.
# 따라서 다음과 같은 계산이 나온다.
# 이전 택시와 겹칠 경우 이동해야하는 거리의 최솟값 = 출발지가 가장 높은 곳의 번호와 도착지가 가장 낮은 번호와의 거리 + 도착지 가장 낮은 번호와 m까지와의 거리 
# 이전택시와 겹치지 않을 경우 이동해야하는 거리의 최솟값 = 이전 택시의 출발지 - 이전 택시의 도착지 + 현재 택시의 출발지 - 이전 택시의 도착지 + 현재 택시의 출발지 - 현재 택시의 도착지
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
taxi = [list(map(int, input().split())) for _ in range(n)]
taxi.sort(key = lambda x: x[1])
max_departure = 0
min_destination = m + 1
distance = m
check = False
for departure, destination in taxi:
    if destination < departure:
        if not max_departure:
            max_departure = departure
            min_destination = destination
            check = True
        elif max_departure < destination:
            distance += 2 * (max_departure - min_destination)
            max_departure = departure
            min_destination = destination
        else:
            max_departure = max(max_departure, departure)
            min_destination = min(min_destination, destination)

if check:
    distance += (max_departure - min_destination) * 2
print(distance)