문제
풀이
전형적인 스위핑 문제이다. 정방향으로 가는 루트는 어찌됐든 무조건 M의 거리를 가야한다. 그러므로 역방향만 고려해주면 되는데, 역방향으로 갈 경우는 내려줬다가 다시 정방향으로 가야되므로 2배를 해준다.
역방향으로 가는 루트들을 list에 넣어준 뒤, 시작점의 내림차순으로 정렬해준다.
스위핑 문제에서 했듯이 루트가 이어지는 경우를 고려하여 선을 계속 이어준 뒤, 끊어질 경우 ans에 그 경로를 더해준다. 끊어진 경우는 최신 루트로 갱신해주어 끝까지 진행해주면 정답을 도출해 낼 수 있다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys
from math import *
N, M = map(int, sys.stdin.readline().split())
list = []
for _ in range(N):
a, b = map(int, sys.stdin.readline().split())
if(a>b): #역방향만 고려
list.append([a, b])
list.sort()
list.reverse() # 시작점이 높은 것으로 정렬, 시작점 내림차순
prevstart = -1
prevend = -1
ans = M
# start > end, prevstart > prevend
for i in list:
start, end = i
if(prevstart == -1 and prevend == -1): # 처음값 입력
prevstart = start
prevend = end
else:
if(prevend <= start):
prevend = min(prevend, end)
else:
ans += 2 * (prevstart-prevend)
prevstart = start
prevend = end
ans += 2 * (prevstart-prevend)
print(ans)
