BOJ 10653 마라톤 2

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

문제

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

마라톤 코스는 N (3 <= N <= 500) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 K 개를 몰래 건너뛰려 한다. (K < N) 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트를 최대 K 개 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

---

입력

첫 번째 줄에 체크포인트의 수 N과 건너뛸 체크포인트의 수 K가 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x 좌표, 두 번째 정수는 y 좌표이다. (-1000 <= x <= 1000, -1000 <= y <= 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원이 한 체크포인트를 건너뛸 때는 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

---

출력

젖소 박승원이 체크포인트 K 개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

---

예제 입력 1

5 2
0 0
8 3
1 1
10 -5
2 2

예제 출력 1

4

---

힌트

젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다.

---

코드

주어진 자원으로는 브루트포스로 문제를 해결할 수 없어서, 바로 DP로 문제를 해결해야 하겠다는 방향은 잡았는데 은근히 구현에 시간이 걸렸다.

코드에서 이차원 배열인 dp[i][j]를 정의했는데 첫 번째 인덱스 i는 도착 체크 포인트를 의미하고, 두 번째 인덱스 j는 건너뛴 체크포인트 개수를 의미한다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int K;
    static Point[] checkPoints;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        checkPoints = new Point[N];
        dp = new int[N][K + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            checkPoints[i] = new Point(x, y);

            // 체크포인트가 동일한 위치에 여러 개 존재 가능해서 이동 거리가 0이 될 수 있으므로
            // 초기값을 MAX_VALUE로 초기화
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        findMinDistance();

        int answer = Arrays.stream(dp[N - 1]).min().getAsInt();

        System.out.println(answer);
    }

    static void findMinDistance() {
        dp[0][0] = 0;

        for (int i = 1; i < N; i++) {
            dp[i][0] = dp[i - 1][0] + calculateDistance(checkPoints[i - 1], checkPoints[i]);

            for (int j = 1; j <= K; j++) {
                int NIdx = i - 1;
                int KIdx = j;
                for (; NIdx >= 0 && KIdx >= 0; NIdx--, KIdx--) {
                    if(dp[NIdx][KIdx] != Integer.MAX_VALUE) {
                        int distanceToCurrent = dp[NIdx][KIdx] + calculateDistance(checkPoints[i], checkPoints[NIdx]);
                        dp[i][j] = Integer.min(dp[i][j], distanceToCurrent);
                    }
                }
            }
        }
    }

    static int calculateDistance(Point p1, Point p2) {
        int difX = Math.abs(p1.x - p2.x);
        int difY = Math.abs(p1.y - p2.y);
        return difX + difY;
    }
}