| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까?
다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ L, R ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 끝점에도 착지가 가능하다. 주헌이가 한 번의 점프로 건너갈 수 있는 최대 거리는 마지막으로 착지한 시점 이후로 건너간 거리와 같다. 단, 점프를 한 적이 없으면 출발한 시점 이후로 건너간 거리와 같다. 예를 들어 주헌이가 점프를 해서 좌표 9에 착지했고 12에서 다시 점프를 한다면, 점프할 수 있는 거리는 최대 3이다.
주헌이가 이동할 수 있는 가장 먼 지점을 구해보자. 단, 점프를 했는데 판자 위에 착지하지 못한 경우는 이동하지 않은 것으로 간주한다.
입력
첫째 줄에 판자의 개수 N 이 주어진다. ( 1 ≤ N ≤ 200,000 )
둘째 줄부터 N개의 줄에 걸쳐서 판자가 놓인 구간을 나타내는 정수 L, R 이 각각 주어진다. ( 0 ≤ L < R ≤ 109 )
L = 0인 판자가 적어도 하나는 주어진다.
출력
주헌이가 최대로 멀리 이동할 수 있는 지점의 좌표를 출력한다.
풀이
스위핑 알고리즘을 활용하면 어렵지 않게 풀 수 있는데 스위핑 알고리즘이라는 걸 모르면 당연히 어렵다. 문제 해결에 필요한 핵심 아이디어는 다음과 같다.
주헌이는 판자 끝에서 점프하지 않아도 된다. 판자 중간의 원하는 지점에서 점프한다면 판자 끝에서 점프 가능한 거리까지의 어느 곳이든 착지 가능하다. 주헌이가 어떤 판자를 밟는데 성공했다면, 이전 판자에서 점프하고 그 판자의 시작 지점을 밟는 것이 항상 가능하다. 점프 가능한 범위 안에 있는 다음 판자의 시작 지점을 밟는 것도 항상 가능하다.
그럼 여기서 필요한 것은 더 이상 앞으로 움직일 수 없는 "판자의 끝에서 점프 가능한 거리"이다. 판자는 겹쳐져있기도 하고 겹쳐진 판자는 점프 없이 지나갈 수 있기 때문에 먼저 입력받은 판자들을 출발 지점에서 가까운 순으로 정렬할 필요가 있다.
정렬이 끝난 판자들을 순차적으로 불러오면서 시작 지점을 확인하고 끝 지점을 기록한다. 다음 판자의 시작 지점이 이전 판자의 끝 지점보다 멀지 않은 경우 판자는 이어져 있는 것이므로 시작 지점은 그대로 두고 끝 지점만 최신화한다.
이 과정을 반복하다가 새 판자의 시작 지점이 이전의 끝 지점보다 멀리 떨어진 경우, 주헌이가 점프해야 하는 구간이 나타난 것이다. 여기서 다음 시작 지점을 기록하기 전에 이전 판자 구간에서 주헌이가 점프 가능한 거리를 확인하자.
이 구간 안의 어느 곳이든 주헌이는 착지할 수 있다. 착지 가능한 최대 거리를 기록한다. 이게 중요한데 여기서 착지 가능한 거리를 저장해두지 않으면 주헌이는 항상 가장 가까운 다음 판자로 점프할 것이고, 밟지 않아야 더 멀리갈 수 있는 판자들을 밟게 되면서 가장 멀리 이동할 수 있는 방법을 찾을 수 없게 된다. 따라서 판자들을 계속 확인하되, 이전에 가장 멀리 갈 수 있었던 판자의 정보를 버리지 않아야 한다.
이렇게 이어진 판자들의 정보, 판자가 완전히 끊어질 때 그 판자 구간에서 착지 가능한 거리를 계속 확인해 나가면 언젠가 새로운 판자의 시작 지점이 이전에 착지 가능한 최대 거리를 넘어서는 판자가 나올 수도 있다. 그 판자는 밟을 방법이 없는 것이므로 현재 기록된 판자의 끝 지점이 가장 멀리 이동할 수 있는 지점이다. 또는 판자를 모두 탐색한 경우도 있는데, 이 경우도 역시 모든 판자를 다 밟을 수 있다는 의미이므로 현재 기록된 판자의 끝 지점이 가장 멀리 이동할 수 있는 지점이다.
정답 코드(python)
import sys
input = sys.stdin.readline
N = int(input())
# 판자 정보를 정렬하여 입력
board = sorted([tuple(map(int,input().split())) for _ in range(N)])
start = 0 # 판자의 시작 지점
end = 0 # 판자의 끝 지점
reach = 0 # 착지 가능한 최대 거리
for i in range(N):
s,e = board[i]
# 현재 판자가 이전 판자와 이어지는 경우
if s <= end:
if end < e:
end = e
# 판자 구간이 끊어진 경우
else:
jump = end * 2 - start
# 현재 판자에서 점프 거리가 이전 최대 거리보다 큰 경우
if reach < jump:
reach = jump
# 새로운 판자의 시작 지점이 착지 가능한 경우
if s <= reach:
start = s
end = e
# 새로운 판자의 시작 지점에 착지할 수 없는 경우
else:
break
print(end)
