목록2024/05 (2)
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..