[백준/10655] 마라톤 1 (Python)

Problem :

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:11:16

 

---

 

문제 설명

 

 

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x좌표, 두 번째 정수는 y좌표이다. (-1000 ≤ x, y ≤ 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

 

출력

 

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

 

입력 예시

 

4
0 0
8 3
11 -1
10 0

 

출력 예시

 

14

 

 

---

 

풀이

 

...어쩌다 보니 더 쉬운 난도의 문제를 역순으로 풀어버렸다. 아래 문제와 비교해 보도록 하자.

 

2023.04.05 - [알고리즘 문제/백준] - [백준/10653] 마라톤 (Python3)

[백준/10653] 마라톤 (Python3)

 

단 여기서 건너뛸 수 있는 체크포인트는 하나이므로, 문제는 훨씬 간단해진다. 단 한 번의 순회를 통해 건너뛸 경우에 경로가 가장 많이 단축되는 체크포인트를 찾으면 되기 때문이다. n번째 체크포인트를 건너뛴다면, 원래 두 지점의 거리 dist(n-1, n), dist(n, n+1)와 체크포인트를 건너뛰었을 경우의 거리 dist(n-1, n+1)의 차를 비교해 볼 수 있겠다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

def distance(a, b) :
  return abs(coord_list[a][0] - coord_list[b][0]) + abs(coord_list[a][1] - coord_list[b][1])

N = int(input())
coord_list = [list(map(int, input().split())) for _ in range(N)]
max_diff = -float('inf')
result = 0
for i in range(N-1) :
  dist = distance(i, i+1)
  result += dist
  if i < N-2 :
    dist2 = distance(i+1, i+2)
    next_dist = distance(i, i+2)
    max_diff = max(max_diff, dist + dist2 - next_dist)

print(result - max_diff)

풀이 완료!