[백준]10655번. 마라톤 1(JAVA)

문제

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

---

풀이

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

public class Main {


    static int n;
    static ArrayList<Point> point = new ArrayList<>();
    /*

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 점의 개수 받기

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 포인트의 x값
            int y = Integer.parseInt(st.nextToken()); // 포인트의 y값
            point.add(new Point(x,y)); // 리스트에 포인트 추가
        }
        
        int maxDistance = Integer.MIN_VALUE; // 최대값을 찾기 위해 최소값으로 초기화
        int maxIdx = 0;

        for(int i = 1; i < n-1; i++){
            int tempDistance = maxDistance(point.get(i), i); // 최대값이 되는 위치 찾기
            if(tempDistance > maxDistance){
                maxDistance = tempDistance;
                maxIdx = i;
            }
        }

        int answer = 0;
        for(int i = 0; i < n-1; i++){
            Point leftPoint = point.get(i); // 본인의 위치
            Point rightPoint = point.get(i+1); // 오른쪽 점
            if(i == maxIdx-1){
                rightPoint = point.get(i+2); // maxIdx와 같은 경우만 i+2의 포인트에 대한 값 설정
                i++; // 한칸 건너뛰기
            }
            answer += Math.abs(rightPoint.x - leftPoint.x) + Math.abs(rightPoint.y - leftPoint.y);
        }
        
        System.out.println(answer);

    }

    private static class Point{ // 점을 저장할 클래스
        int x;
        int y;

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

    private static int maxDistance(Point p, int idx){ // 기존의 좌우 거리, 없을 때의 거리에 대한 값을 구하는 메서드
        Point leftPoint = point.get(idx-1);
        Point rightPoint = point.get(idx+1);

        int leftDistance = Math.abs(p.x - leftPoint.x) + Math.abs(p.y - leftPoint.y);
        int rightDistance = Math.abs(p.x - rightPoint.x) + Math.abs(p.y - rightPoint.y);
        int absentDistance = Math.abs(rightPoint.x - leftPoint.x) + Math.abs(rightPoint.y - leftPoint.y);
        int distance = Math.abs((leftDistance+rightDistance) - absentDistance);
        return distance;
    }


}

 

기존의 좌우 점에 대한 거리와 그 점이 없을 시에 거리의 차이가 가장 큰 점을 빼주는 것이 좋기 때문에 이를 계산한 뒤에 값을 구한다.