백준 10653 - 마라톤 2 (Java)

문제

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

마라톤 코스는 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

 

풀이

DP 배열은 2차원으로, dp[k][i]는 i번째까지 도달하면서, k번을 건너 뛰었을 때의 최솟값으로 잡았다.

그 후 고려해야 하는 점은

dp[k][i-1] + i-1과 i번째의 거리

위 경우에는 모두 다 건너뛰어서 더이상 건너 뛸 수 없기 때문에, 직전까지 최소 거리 + 가야할 거리를 더한다.

위 처럼 몇번 건너 뛰었는지에 따라 i-1가 될지, i-2가 될지 정해져야 한다는 것.

그럼 dp[k][n] 는 dp[k-1][N-i-1] + 현재 가야할 거리 가 된다.

위 점화식을 토대로 문제를 해결하면 된다.

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

public class BJ_10653_마라톤2 {
    public static class Point{
        int x;
        int y;
        Point(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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Point[] points = new Point[N];
        int dp[][] = new int[K+1][N];

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

        for(int i=0; i<=K; i++)
        {
            Arrays.fill(dp[i],-1);
            if(i==0)dp[i][0]=0;
        }

        int min, temp;
        for(int i=1; i<N; i++){
            for(int j=0; j<=K; j++)
            {
                if(i-j>0){
                    min = Integer.MAX_VALUE;
                    for(int k=0;k<=j;k++)
                    {
                        temp = dp[j-k][i-k-1];
                        if(temp==-1) continue;
                        int distance = Math.abs(points[i-k-1].x-points[i].x) + Math.abs(points[i-k-1].y-points[i].y);
                        min = Math.min(min, temp+distance);
                    }
                    dp[j][i] = min;
                }
            }
        }
        int result = dp[0][N-1];
        for(int i=1; i<=K; i++)
        {
            result = Math.min(result,dp[i][N-1]);
        }
        System.out.println(result);

    }
}