백준 #2156. 포도주시식: DP / 실버1

문제 링크 : https://www.acmicpc.net/problem/2156

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

<조건>

1. 선택한 잔의 포두주는 모두 섭취 ,마신 뒤 원상복귀
2. 연속으로 놓여진 3잔 모두 섭취 불가

<문제 유형 : DP >

1. 최대값 문제
2. 연속된 3잔 섭취 불가 →이전 ,전전 까지 현재 뿐만 아니라 전체 상황을 고려해함

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

dp [i] : 현재 섭취 포도주량 최대 값

1. 현재 O, 이전 O , 전전 X ⇒ cups[i] + cups[i-1] + dp[i-3]
2. 현재 O , 이전 x , 전전 O ~ ⇒ cups[i] + dp[i-2]
3. 현재 x , 이전 o or not (이전 O 전전 O ) ~ ⇒ dp[i-1]

dp[i] = max(cups[i] + cups[i-1] + dp[i-3] , cups[i] + dp[i-2] , dp[i-1])