A - Frog 1 / atcoder.jp

문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_a
답 자바 코드 링크 : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/A%20-%20Frog%201/src/Main.java

$$
코드에서\quad 배열\quad v[i]\quad : \quad개구리가\quad i번째\quad stone에\quad 도달하는\quad 최소비용
$$

이 문제를 식으로 풀어 보면 배열 v[i] 는 아래와 같이 계산됩니다.

$$
v_i = min(abs(s_{i-1} - s_{i}) + v_{i-1}, abs(s_{i-2} - s_i) + v_{i-2})
$$

import java.util.Scanner;

// A - Frog 1 / atcoder.jp
// 문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_a

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

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

        int r = minimumTotalCost(stones, N);
        System.out.println(r);
    }

    public static int minimumTotalCost(int[] s, int N) {
        int[] v = new int[N];
        v[0] = 0;
        v[1] = Math.abs(s[0]-s[1]);

        for(int i=2; i<N; ++i) {
            // 위의 수식을 코드로 바꾸면, 아래와 같습니다.
            v[i] = Math.min(Math.abs(s[i-1]-s[i]) +v[i-1], Math.abs(s[i-2]-s[i]) +v[i-2]);
        }

        return v[N-1];
    }
}