백준 10653 (마라톤 2) - java

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

10653번: 마라톤 2

유형 : DP

접근

• 최대 K개 건너 뛸수 있기 때문에 마지막 지점에서 0개부터 n개 까지 건너 뛴 거리 중 최솟값을 구해주면 된다.
• dp 배열을 2차원으로 설정한다.
  • dp[i][j] : i의 값은 i번째 지점 , j의 값은 건너 뛴 말의 개수 , dp[i][j]는 즉 j개의 말을 건너뛰고 i번째 지점에 도착했을 때 최소 거리이다.

 

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;

    static int[][] board;

    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());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][2];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            board[i][0] = x;
            board[i][1] = y;
        }

        int[][] dp = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        dp[1][0] = 0; // i 지점까지 j개를 건너뛴 최소 값

        for(int i=2;i<=n;i++){

            dp[i][0] = dp[i-1][0] + dis(board[i],board[i-1]);

            for(int j=1;j<=m;j++){

                int idx = j;

                for(int k=i-1;k>=1;k--){

                    if(dp[k][idx] != Integer.MAX_VALUE){
                        dp[i][j] = Math.min(dp[i][j], dp[k][idx] + dis(board[i], board[k]));
                    }

                    idx = idx - 1;

                    if(idx < 0)
                        break;
                }

            }
        }

        int result = Integer.MAX_VALUE;
        for(int i=0;i<=m;i++){
            result = Math.min(result , dp[n][i]);
        }
        System.out.println(result);
        br.close();
    }

    

    static int dis(int[] x1,int[] x2){
        return Math.abs(x1[0] - x2[0]) + Math.abs(x1[1] - x2[1]);
    }
}