접근 방법 : 브루트 포스
처음에 deepcopy를 써서 전체에서 하나 씩 삭제한 뒤, 합을 구하려 했는데 실패했다.
전체 합에서 체크 포인트 하나 빼기 위한 최대 포인트 계산 값을 확인
뺄 체크 포인트 기준은 제일 큰 게 빠졌을 때 최소가 되니 최대값을 구해준다.
# -*- coding: utf-8 -*-
import sys
N = int(sys.stdin.readline().strip())
check_list = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
check_dist = 0
total_sum = 0
for i in range(N - 1):
total_sum += abs(check_list[i][0] - check_list[i + 1][0]) + abs(check_list[i][1] - check_list[i + 1][1])
for i in range(1, N - 1):
left_dist = abs(check_list[i - 1][0] - check_list[i][0]) + abs(check_list[i - 1][1] - check_list[i][1])
right_dist = abs(check_list[i + 1][0] - check_list[i][0]) + abs(check_list[i + 1][1] - check_list[i][1])
skip_dist = abs(check_list[i + 1][0] - check_list[i - 1][0]) + abs(check_list[i + 1][1] - check_list[i - 1][1])
sub_dist = left_dist + right_dist - skip_dist
check_dist = max(check_dist, sub_dist)
print(total_sum - check_dist)