[백준 10655번] 파이썬 - 마라톤1

백준 10655_마라톤1

시간 제한 1초, 메모리 제한 256MB

조건

• 농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.
• 마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다.
• 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다.
  • 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.
• 젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?
• 참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다.
• 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

접근 방법

• 입력을 받아주며 1개의 리스트를 더 생성해준다.
  • 현재 체크포인트와 직전 체크포인트와의 거리 1개
• 이후, 1번과 N번을 제외하고 for문을 돌면서 아래 계산을 수행해준다.
  • 전체 누적거리 - 뛰어지나칠 체크포인트가지의 거리 -> dist[i], dist[i+1]
  • 이후 + arr[i-1]과 arr[i+1]의 멘허튼 거리를 더해주면 된다.
• 최소값은 항상 갱신!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


N = int(input())  
arr = []  
dist = [0] * N  
sum_dist = [0] * N  

for i in range(N):  
    a, b = map(int, input().split())  
    arr.append((a,b))  
    if i > 0:  
        dist[i] = abs(arr[i][0]-arr[i-1][0]) + abs(arr[i][1]-arr[i-1][1])  
        sum_dist[i] = dist[i-1] + dist[i]  

result = float('inf')  
sum_dist = sum(dist)  
for j in range(1, N-1):  
    # 전체 누적거리에서, 뛰어넘을 체크포인트로 통하는 경로 비용 빼주고 -> 직전 체크포인트에서 현재, 현재에서 다음 체크포인트까지의 거리  
    # 새로운 경로 비용 더해주기 -> 직전에서 다음까지  
    val = sum_dist - dist[j] - dist[j+1] + (abs(arr[j-1][0] - arr[j+1][0]) + abs(arr[j-1][1] - arr[j+1][1]))  
    if val < result:  
        result = val  

print(result)