[Python] 백준 10655번 마라톤 1 - 구현

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준 10655번 : 마라톤 1

10655번: 마라톤 1

---

문제

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

마라톤 코스는 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개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

 

예제 입력 1	예제 출력 1
4 0 0 8 3 11 -1 10 0	14

 

내 코드 - 오답

배열 가운데 값 중, 이 전 배열 값과 이 후 배열 값의 합이 제일 큰 수를 빼고 계산 

import sys

input = sys.stdin.readline

# n 이 3 이상이므로 모든 경우의 수를 구할 필요는 없다.
n = int(input())
data = []
for i in range(n):
  x, y = map(int, input().split())
  data.append((x, y))

result = 0
max = 0
for i in range(1, n - 1):
  after_data = abs(data[i][0] - data[i + 1][0]) + abs(data[i][1] - data[i + 1][1])
  before_data = abs(data[i - 1][0] - data[i][0]) + abs(data[i - 1][1] - data[i][1])
  if max <= after_data + before_data: 
    max = after_data + before_data
    max_x = data[i][0]
    max_y = data[i][1]

data.remove((max_x, max_y))

for i in range(1, n - 1):
  result = result + abs(data[i - 1][0] - data[i][0]) + abs(data[i - 1][1] - data[i][1])
print(result)

 

2차 코드 - 정답

remove 를 코드화 

import sys
input = sys.stdin.readline

# n 이 3 이상이므로 모든 경우의 수를 구할 필요는 없다.
n = int(input())
data = []
for i in range(n):
  x, y = map(int, input().split())
  data.append((x, y))

maxValue = 0

for i in range(1, n-1):
  after_data = abs(data[i][0] - data[i + 1][0]) + abs(data[i][1] - data[i + 1][1])
  before_data = abs(data[i - 1][0] - data[i][0]) + abs(data[i - 1][1] - data[i][1])
  value = after_data + before_data - (abs(data[i - 1][0] - data[i + 1][0]) 
  + abs(data[i - 1][1] - data[i + 1][1]))
  maxValue = max(value, maxValue)

maxX = data[0][0]
maxY = data[0][1]

totalValue = 0

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

print(totalValue - maxValue)