atcoder.jp
-
D - Knapsack 1 / atcoder.jpatcoder.jp 2019. 12. 27. 19:12
문제링크 : https://atcoder.jp/contests/dp/tasks/dp_d Submission : https://atcoder.jp/contests/dp/submissions/9158698 Java code : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/D%20-%20Knapsack%201/src/Main.java import java.io.*; import static java.lang.Long.max; // D - Knapsack 1 / https://atcoder.jp // 문제링크 : https://atcoder.jp/contests/dp/tasks/dp_d // Submission : https://atcoder.jp/cont..
-
C - Vacation / atcoder.jpatcoder.jp 2019. 12. 27. 17:35
문제 링크 : https://atcoder.jp/contests/dp/submissions/9157155 답 링크(속도 최적화 하기전) : https://atcoder.jp/contests/dp/submissions/9157155 답 링크(속도 최적화된) : https://atcoder.jp/contests/dp/submissions/9157155 자바 코드 : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/C%20-%20Vacation/src/Main.java 문제 정의에 따라서 a, b, c 를 아래와 같이 가정하고, \begin{aligned} a = 0, b = 1, c = 2 \\ 1 \leq N \leq 10^5 \\ (1 \leq i \l..
-
B - Frog 2 / atcoder.jpatcoder.jp 2019. 12. 26. 19:49
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..
-
A - Frog 1 / atcoder.jpatcoder.jp 2019. 12. 26. 16:10
문제 링크 : 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 / a..