atcoder.jp
A - Frog 1 / atcoder.jp
건이두
2019. 12. 26. 16:10
728x90
문제 링크 : 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];
}
}
728x90