[Codetree] 마라톤 중간에 택시타기 2

17 Sep 2026

Reading time ~2 minutes

풀이1 구현
풀이2 구현

해당 문제는 코드트리 마라톤 중간에 택시타기 2에서 풀어보실 수 있습니다.

풀이1 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }

        // Please write your code here.
        int min = Integer.MAX_VALUE;

        for(int i = 1; i < n - 1; i++) {
            int tmpX = x[i], tmpY = y[i];
            x[i] = x[i-1]; y[i] = y[i-1]; // 건너뛰기 위해 이전 위치랑 똑같은 위치로 변경
            min = Math.min(min,getDist(x,y)); // 최소값 계산
            x[i] = tmpX; y[i] = tmpY; // 원상복구
        }

        System.out.println(min);
    }

    static int getDist(int[] x, int[] y){
        int n = x.length;
        int sum = 0;
        for(int i = 0; i < n - 1; i++) {
            sum += Math.abs(x[i]-x[i+1])+Math.abs(y[i]-y[i+1]);
        }
        return sum;
    }
}

위치마다 건너뛰는 방법을 스스로 생각해내지 못했다. 구글링하여 이전 위치와 똑같은 위치로 하여 계산하면 된다는 것을 깨달았다.

풀이2 구현

import java.util.Scanner;

public class Main {    

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 변수 선언 및 입력
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        
        for(int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        
        int min = Integer.MAX_VALUE;

        // 각 스킵할 포인트(skipPoint)를 건너뛰었을 때의 거리를 구해라.
        for(int skipPoint = 1; skipPoint < n - 1; skipPoint++) {
            int dist = 0;
            int currentPoint = 0;

            for(int nextPoint = 1; nextPoint < n; nextPoint++) {
            	// 다음 체크포인트가 스킵할 포인트이면 건너뛰어라.
                if(nextPoint == skipPoint) continue;
                // 현재 체크포인트에서 다음 체크포인트까지의 거리를 구해라.
                dist += Math.abs(x[currentPoint] - x[nextPoint]) + Math.abs(y[currentPoint] - y[nextPoint]);
                // 다음 구간의 거리를 구하기 위해 현재 체크포인트를 갱신. 
                currentPoint = nextPoint;
            }
            
            min = Math.min(min, dist);
        }
        
        System.out.println(min);
    }
}

완전탐색