Next dream Next dream

문제링크 : https://algospot.com/judge/problem/read/FESTIVAL 제출링크 : https://algospot.com/judge/submission/detail/653190 자바 소스 : https://github.com/skysign/WSAPT/blob/master/algospot.com/FESTIVAL/src/Main.java 문제는 2가지 기법을 묻는 문제입니다. prefix sum 여기를 참고하세요 → https://skysign.tistory.com/171 평균의 구간이 band수에서 시작해서, N까지 증가합니다. import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOExc..

문제링크 : https://www.acmicpc.net/problem/11726 제출링크 : https://www.acmicpc.net/source/17183178 자바 소스 : https://github.com/skysign/WSAPT/blob/master/BOJ/11726%EB%B2%88%202%C3%97n%20%ED%83%80%EC%9D%BC%EB%A7%81/src/Main.java import java.util.Scanner; public class Main { public void solve() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] d = new int[N+1]; d[1] = 1; if(N>=2) d[2] = 2;..

문제링크 : https://www.acmicpc.net/problem/9095 제출링크 : https://www.acmicpc.net/source/17177201 자바 소스 : https://github.com/skysign/WSAPT/blob/master/acmicpc.net/11726%EB%B2%88%202%C3%97n%20%ED%83%80%EC%9D%BC%EB%A7%81/src/Main.java 점화식이 딱히 떠오르지 않아서, 그냥 손으로 5번까지 해봤는대, 왠지 d_i = d_i-1 + d_i-2 + d_i-3 인것 같습니다. d_7 으로 테스트 해봤더니 44가 나와서, 이 식으로 풀어 봤습니다. d_1 = 1 : 1 d_2 = 1+1 : 2 d_3 = 1+1+1, 2+1, 1+2, 3: 4 d_..

문제링크 : https://www.acmicpc.net/problem/2579 제출링크 : https://www.acmicpc.net/source/17179222 Java source : https://github.com/skysign/WSAPT/blob/master/acmicpc.net/2579%EB%B2%88%20%EA%B3%84%EB%8B%A8%20%EC%98%A4%EB%A5%B4%EA%B8%B0/src/Main.java 피보나치수열과 비슷한 문제인대요, 한가지만 주의 하면 됩니다. d_i-1 + st_i → d_i d_i-2 + st_i → d_i 이렇게 이동 하면, 3칸을 연속으로 밟으면 안된다, 라는 룰을 지킬 수가 없어요 그래서 약간 변경해서, 아래와 같이 이동하면 룰을 지킬 수 있습니다. ..

문제링크 : https://atcoder.jp/contests/dp/tasks/dp_n 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9653540 Java source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/N%20-%20Slimes/src/Main.java 여러개의 슬라임을 2개씩 합칠 때, 합치는 비용을 고려해서, 가장 적은 비용으로 합치는 방법을 찾는 문제입니다. 이 문제를 DP가 방식이 아니라, 아주 간단하게 생각해서, 인접한 두수의 합이 최소가 되는 방식으로, 2개의 슬라임을 합처나가면, 최..

문제링크 : https://atcoder.jp/contests/dp/tasks/dp_l 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9546944 Java source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/L%20-%20Deque/src/Main.java 리스트가 주어지고, 두 플레이어가, 이 리스트의 가장 앞/뒤 중에 하나를 서로 빼게 됩니다. 플레이어 타로/지로에 따라서, 뺀수는 타로는 X, 지로는 Y에 더하게 되구요, X-Y 값을 찾는 문제입니다. 문제를 풀기에서 앞서서, 타로와 지로가 숫자를..

문제링크 : https://atcoder.jp/contests/dp/tasks/dp_k 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission 첫버전 : https://atcoder.jp/contests/dp/submissions/9509087 Submission 속도최적화 : https://atcoder.jp/contests/dp/submissions/9543565 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/K%20-%20Stones/src/Main.java K - Stones 문제입니다. 문제 설명이 약간 모호할 수도 있는대, Sample input 1을 가지고 문제를..

문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_i 문제 해설 : https://jinpyo.kim/EducationalDP-solution https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp https://www.youtube.com/watch?v=jbA8fPaiYtQ Submission : https://atcoder.jp/contests/dp/submissions/9313650 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/I%20-%20Coins/src/Main.j..