목록2024/05/17 (1)
delpho
[실버1, DP] 백준 2156 - 포도주 시식 (자바)
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
2024. 5. 17. 09:12