[Baekjoon 10655 / Java / 실버3] 마라톤 1

import java.io.*;

import java.util.*;

public class 마라톤1_10655 {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       

        // 체크포인트 입력받기

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

        int cp[][] = new int[N][2];

        for(int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            cp[i][0] = Integer.parseInt(st.nextToken());

            cp[i][1] = Integer.parseInt(st.nextToken());

        }

        int distance = 0;

        int diff = 0;

        int point;

        int point2;

        int point3;

        for(int i = 0; i < N - 1; i++) {

            point = Math.abs(cp[i][0] - cp[i+1][0]) + Math.abs(cp[i][1] - cp[i+1][1]);

            distance += point;

            if(i == N - 2) {

                break;

            }

            point2 = Math.abs(cp[i+1][0] - cp[i+2][0]) + Math.abs(cp[i+1][1] - cp[i+2][1]);

            point3 = Math.abs(cp[i][0] - cp[i+2][0]) + Math.abs(cp[i][1] - cp[i+2][1]);

            if(diff < Math.abs(point + point2) - point3) {

                diff = Math.abs(point + point2) - point3;

            }

        }

        distance -= diff;

        System.out.println(distance);

    }

}

 

문제 자체는 간단한데, 이상하게 자꾸 꼬여서 애먹은 문제이다.

 

(i -> i+1 + i -> i+2) - (i -> i+2) 값이 가장 큰 부분을 찾아서, 그걸 총 거리에서 빼주면 된다.

예를 들어,

i

i + 1

i + 2

 

이렇게 3개의 체크포인트가 있을 때, i + 1을 거쳐가는 거리와 건너뛰는 거리의 차이를 구한다.

이 거리의 차이는 "체크포인트를 건너뛰었을 때 아껴지는 거리" 이며, 이 값이 가장 높은 경우를 찾으면 되는 것이다.