[백준 2836번] 수상 택시 (Python3)

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

taxi = []
for i in range(N):
  x,y = map(int,input().split())
  if y>x:
    continue
  taxi.append((M-x,M-y))
taxi.sort()
t = len(taxi)

SUM = 0
x = 0
while x < t:
  start,end = taxi[x]
  next = x
  while next+1<t and taxi[next+1][0]<end:
    next += 1
    end = max(taxi[next][1],end)
  SUM += end-start
  x = next+1

print(M+SUM*2)

 

투 포인터 알고리즘으로 해결하였다.

일단 이 문제에서는 정주행하는 사람은 고려할 필요가 없다. 왜냐하면 어차피 M까지 가는 동안 내려주면 되기 때문이다.

따라서 역주행하는 사람들만을 고려하는 것이 포인트다.

 

요약하면,

1. 입력값 중에서 도착지가 출발지보다 작은 역주행하는 경우만 저장한다.

2. 출발지점을 기준으로 정렬한다.

3. 역주행하는 경우들 중에서 겹치는 부분을 제외한 나머지 부분들의 길이의 합을 투포인터 알고리즘으로 구한다.

 

 

오늘의 교훈) 열심히하자