delpho

1. dp 문제를 읽고 항상 떠오르는 생각은, 이걸 DP로 어떻게 풀라는거지? 라는 생각이다... 아직 경험치가 많이 부족한가보다2. 완전탐색을 하지 않고 dp 점화식을 어떻게 세울 수 있을지 아이디어가 전혀 떠오르지 않았다.3. dp[i]의 정의는, i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양 이다.4.점화식은 dp[i]=max(dp[i−1],dp[i−2]+wine[i],dp[i−3]+wine[i−1]+wine[i]) 다.5. i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양을 구하기 위해서는, 즉, dp[i]를 구하기 위해서는, 세가지 경우를 고려해야한다.6. (1) 현재 i번째의 와인잔을 마시지 않는 경우 (i-1번째까지의 마실 수 있는 최대 와인 양)    (2) i-2번째까지..

DP 문제는 아직도 참 어렵당 00과 1로 타일을 만들 수 있는 수열의 개수를 구하는 문제다. https://www.acmicpc.net/board/view/84734 에서 letusshow님의 답변이 너무 좋았다. 해당 답변을 보니 이 문제의 풀이가 와닿았다. 타일을 만들 수 있는 경우는 2가지.1. 00 타일이 오는 경우 - 00...으로 시작2. 1 타일이 오는 경우 - 1...로 시작 길이가 N인 이진 수열의 개수'를 f(N)이라고 정의하면 f(N) = f(N-1) + f(N-2) 또한 f(0) = f(1) = 1임을 확인   제출 코드import java.util.*;import java.io.*;public class testtest { static int N; static Inte..

Think 1. 하 DP.... 정말 어렵다 문제에 주어진 조건을 성립하면서 DP로 푸려는 아이디어가 어려웠다. 2. https://st-lab.tistory.com/132 를 참고했다. 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class test { static int n; static int sequence[]; static Integer dp[]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); stat..

Think 1. LIS인 이 문제를 보고 고민해보았으나, 풀이 접근 방법이 떠오르지 않음 (이걸 dp로 어떻게 풀지..? 라는 생각) 2. https://st-lab.tistory.com/137 를 참고하여 풀이 방법을 공부함 3. 현재 수열 기준으로 이전 값들을 탐색하며 이전 값이 더 작다면 해당 인덱스의 dp 값 + 1과 현재 dp값을 비교하여 최대값을 저장해준다 4. 해당 풀이법은 시간복잡도가 N^2라고 하며, 이분탐색을 활용하면 NlogN까지 가능하다고 함 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public..