B - Frog 2 / atcoder.jp

A - Frog 1을 푸셨다면 충분히 풀 수 있는 문제입니다.

\begin{aligned}
문제 정의에 따라서, 2\leq N \leq 10^5 \\
v_i : i 번째\quad 까지도착하는대\quad 도달하는\quad 최소\quad 비용 (0 \leq i < N) \\
h_i 는 각 돌의 이동 비용 \\
v_i = min(abs(h_{i-k}-h_i)+v_{i-k}) \quad 1 \leq k < K \quad and \quad i-k \geq 0 \\
\end{aligned}

    import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int K = sc.nextInt();
            int[] h = new int[N];

            for(int i=0; i<N; ++i) {
                h[i] = sc.nextInt();
            }

            int r = jump(N, K, h);
            System.out.println(r);
        }

        public static int jump(int N, int K, int[] h) {
            int[] v = new int[N];

            K = Math.min(N-1, K);

            for(int j=1; j<N; ++j) {
                int t = Integer.MAX_VALUE;
                boolean bContinue = true;
                for(int d=1; d<=K && bContinue; ++d) {
                    int i = j-d;
                    if(i>=0){
                        t = Math.min(Math.abs(h[i]-h[j]) + v[i], t);
                    }
                    else {
                        bContinue = false;
                    }
                }

                v[j] = t;
            }

            return v[N-1];
        }
    }