https://www.acmicpc.net/problem/10655

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

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

풀이 아이디어

n개의 체크포인트가 있는데 모든 체크포인트를 지난다고 가정했을 때의 "총 거리"를 구한다.
그리고 처음과 마지막을 제외한 2~n-1번째 체크포인트 중 각각을 건너뛸 때 단축되는 단축량을 구하고 배열에 저장한다. (체크포인트는 인덱스로는 1~n-2)
구한 절약량 중에서 "제일 큰 단축량"을 총 거리에서 빼준다.
총 거리 - 제일 큰 단축량 = 정답

i번째 체크포인트를 건너뛸 때 단축되는 거리는
체크포인트 a에서 b까지의 거리를 distance[a][b]라고 하면
단축되는 거리 = distance[i-1][i]+distance[i][i+1]-distance[i-1][i+1]이다.
예를 들어 체크포인트 1->2->3->4가 있다면
2를 건너뛴다면 1->3->4를 가게 되는데
이때 절약되는 거리는 (1->2->3)-(1->3)가 된다.

풀이 코드

import java.io.*;
import java.util.*;

public class _10655 {
    public static void main(String[] args) throws IOException{
        // 입력값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] points = new int[n][2];
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            points[i][0] = Integer.parseInt(st.nextToken());
            points[i][1] = Integer.parseInt(st.nextToken());
        }
        br.close();
        
        // 모든 체크포인트를 지날 때의 전체 거리 구하기
        int totalDistance = 0;
        int start_x = points[0][0];
        int start_y = points[0][1];
        for(int i=1;i<n;i++){
            totalDistance += Math.abs(start_x - points[i][0]) + Math.abs(start_y - points[i][1]);
            start_x = points[i][0];
            start_y = points[i][1];
        }

        // i번째 체크포인트를 빼면서 절약되는 거리 구하기 
        int[] saveDistances = new int[n];
        int saveDistance = 0;
        for(int i=1;i<n-1;i++){
            int beforeJump = Math.abs(points[i-1][0] - points[i][0]) + Math.abs(points[i-1][1] - points[i][1]) + Math.abs(points[i][0] - points[i+1][0]) + Math.abs(points[i][1] - points[i+1][1]);
            int afterJump = Math.abs(points[i-1][0] - points[i+1][0]) + Math.abs(points[i-1][1] - points[i+1][1]);
            saveDistance = beforeJump - afterJump;
            saveDistances[i] = saveDistance;
        }

        System.out.println(totalDistance - Arrays.stream(saveDistances).max().getAsInt());
    }
}