[BOJ2156] 포도주 시식

가장 많은 포도주를 마실 수 있도록 하는 법

• 포도주 잔 선택하면, 마신 후 그 자리에
• 연속으로 놓여있는 3잔 마시기 불가능
• 1부터 n까지 번호 붙은 포도주가 순서대로 테이블 위에
• 가장 많이 마실 수 있는 양

입력

• 포도주 잔 개수 n(1<= n <= 10,000)
• 포도주 양은 1,000 이하 음수 아닌 정수

출력

• 최대로 마실 수 있는 포도주 양

설계

• 연속 세 잔 마시기 불가능하므로, (1) 두 잔까지 연속 가능, (2) 아니면 두 칸 뒤의 잔 마시기
• dp[i] = max(wine[i] + wine[i-1] + dp[i-3], wine[i] + dp[i-2])
• Boj2579 계단오르기랑 핵심 알고리즘 같음

피드백

• 계단오르기랑 조금 다른 건, 포도주는 두 잔 연속 스킵도 가능하다는 것 TestCase) 100, 200, 1, 3, 4, 400 -> 최대값 (703이 아닌 704)
• 따라서, 각 포도주의 위치에서의 최대값을 계속 갱신 필요 (마시지 않아도)
• dp[i] = max(dp[i], dp[i-1]) 현재와 이전 값 비교하여 갱신

How I solved(click to github)

---

ref :
BOJ2156