[백준/Java] 10655번 마라톤 1

-Code

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

public class BOJ10655 {
    static class Pos {
        int x, y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        Pos[] checkPoints = new Pos[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            checkPoints[i] = new Pos(x, y);
        }
        // 총 거리 계산
        int totalDist = 0;
        for (int i = 1; i < n; i++) {
            totalDist +=
                    getDist(checkPoints[i - 1], checkPoints[i]);
        }
        // 스킵할때 거리차가 큰 경우 구하기
        int maxSkip = 0;
        for (int i = 1; i < n - 1; i++) {
            int skipBefore = getDist(checkPoints[i - 1], checkPoints[i]) + getDist(checkPoints[i], checkPoints[i + 1]);
            int skip = getDist(checkPoints[i - 1], checkPoints[i + 1]);
            maxSkip = Math.max(maxSkip, skipBefore - skip);
        }
        System.out.println(totalDist - maxSkip);
    }
    // 거리 구하는 메소드
    private static int getDist(Pos pos1, Pos pos2) {
        return Math.abs(pos1.x - pos2.x) + Math.abs(pos1.y - pos2.y);
    }
}

처음에는 하나하나 값을 직접 뺀 총거리를 구해서 O(n ^ 2)가 나와서 틀렸었습니다. 그래서 힌트로 총거리에서 빼주는 것을 보고 작정했으나 너무 단순하게 생각해 각 1개의 구간만 빼면 되겠지 했으나 잘못된 이해였습니다.

그래서 생각을 정리한 결과 특정한 지점을 건너뛴다고 했을 때, 우리가 실제로 삭제하는 경로와 새로 연결하는 경로를 구분해야서 계산해야 했습니다.

• 원래 가야 했던 길: (i-1,  i) 거리 + (i, i+1) 거리
• 새로 생긴 지름길: (i-1, i+1) 거리
• 최종 이득: (원래 거리) - (지름길 거리)

이렇게 3개로 나누어서 원래 길에서 지름길을 빼주어 그 값중 가장 큰 값을 찾아 총거리에서 빼주면 되는 문제였습니다.