Next dream Next dream

문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_g 문제 해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9268425 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/G%20-%20Longest%20Path/src/Main.java Educational DP Contest에서 그래프 문제가 처음 나왔습니다. 우선 단어의 뜻을 잘 이해할 필요가 있습니다. -directed : 한쪽 방향으로만 이라는 뜻이구요, -edge가 1→2 이렇게 1에서 2로가는 것만 ..

F - LCS / atcoder.jp 문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_f 문제 해설 : https://jinpyo.kim/EducationalDP-solution 이번 풀이는 참고했던 문제해설과는 약간 다른게 풀어졌습니다. Submission : https://atcoder.jp/contests/dp/submissions/9250597 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/F%20-%20LCS/src/Main.java LCS 문제입니다. LongestLongest common subsequence 문제입니다. Longest common substring은 다른 문제..

문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_e 문제 해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/10059004 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/E%20-%20Knapsack%202/src/Main.java 이전 문제인 'D - Knapsack 1'의 풀이를 그대로 적용하면, Sample Input 1~3에서는 올바른 값이 나올 수도 있지만, 실제 이 문제는 약간 다른 방식으로 접근해야 합니다. 문제의 Constrain..

문제링크 : 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..

문제 링크 : 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..

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..

Hamiltonian Path / geeksforgeeks.org 주의사항 1 8 이렇게 되어 있어도, 1,8 8,1 2개의 방향 모두 이동 가능함 시작이 항상 1부터가 아니고, 모든 vertex에서 시작할 수 있음 문제 링크 : https://practice.geeksforgeeks.org/problems/hamiltonian-path/0 문제 해설 : https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/ 정답 코드 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Hamiltonian%20Path/src/GFG.java import java.util.Scanner; // Ha..

사실 풀기는 어제 저녁에 풀었는대, 오늘 올리네요... 점점 게을러 저서 큰일입니다. ps : 어제 시켰던 삼겹살은 맛있었다는 ㅋㅋ 문제 링크 : https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0 문제 해설 : https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ 정답 자바 소스 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Nth%20Fibonacci%20Number/src/GFG.java import java.util.Scanner; // Nth Fibonacci Number / geeksforgeeks..