시간 복잡도 줄이는 기술 4. LR 배열

마라톤 중간에 택시타기

마라톤 코스는 N개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 마라톤이 끝납니다. 게으른 개발자 A는 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한 개를 몰래 건너뛰려 합니다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 티가 많이 나기 때문에 이 두 체크포인트는 건너뛰지 않으려고 합니다. 개발자 A가 체크포인트 한 개를 건너 뛰어서 마라톤을 완주하려고 할 때, 최소 거리를 구하는 프로그램을 작성해보세요.

단, 거리 계산은  ∣x1−x2∣+∣y1−y2∣ 로 계산하는 것을 의미합니다. 또한, 체크 포인트의 좌표는 겹쳐져 주어질 수도 있으며, 이 경우 개발자 A가 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰게 되며 그 점에 있는 모든 체크포인트를 건너뛰지 않음에 유의합니다.

 

아이디어

• 마지막에 L[i-1]+R[i+1] 에 i-1 → i+1로 가는 길이를 더해주는 것이 포인트

코드

#일반 for 문: 숫자가 주어질 때마다 남은 숫자 N - 1개를 순회해야 하므로 O(N) 
#L배열 Q(N), R배열 Q(N) 질의마다 시간 복잡도 O(1), Q개 질의 -> 총 Q(Q+N)

n=int(input())
check_point= [tuple(map(int,input().split())) for _ in range(n)]

L=[0]*n 
R=[0]*n 
for i in range(n-1):
    L[i+1]= L[i]+abs(check_point[i][0]-check_point[i+1][0]) + abs(check_point[i][1]-check_point[i+1][1])

for i in range(n-1,0,-1):
    R[i-1]= R[i]+abs(check_point[i][0]-check_point[i-1][0]) +abs(check_point[i][1]-check_point[i-1][1])

ans=1e9

for i in range(1,n-1):
    #1까지의 합 + 3~4까지의 합 + 1->3가는 합 
    ans=min(ans,L[i - 1] + R[i + 1]+abs(check_point[i + 1][0] - check_point[i - 1][0]) +abs(check_point[i + 1][1] - check_point[i - 1][1]))

print(ans)