[백준] 2156번 포도주 시식

이 문제도 진짜 어려웠다. 계단 오르기 처럼 하면 될 줄알았는데, 예상외로 변수가 많았다. 

일단 잔이 1개 있다면, 그 1잔이 바로 최댓값이다. dp[1] = arr[1]

잔이 2개있다면 2개를 마시는게 최댓값이다. dp[2] = arr[1] + arr[2]

잔이 3개있다면? 여기서부터 문제인데 바로 연속으로 3잔은 마실 수 없는것이다.

이제 점화식을 풀어보자

1) N번째로 마시는 포도주를 안마시겠다면?

N번째 포도주가 양이 적어 건너뛰는게 나을 수도있다.

이럴땐 dp[N] = dp[N-1] (N번째를 마시지 않았으므로)

2) N번째로 마시는 포도주가 1번 연속이라면?

1번 연속이다라는건 앞의 포도주를 건너뛰고 처음으로 마셨다는 뜻이다

그럼 n-1번째는 절대 마시면 안된다. 대신 n-2번째는 마시든 말든 상관없다.

이럴땐 dp[N] = dp[N-2] + arr[N]

3) N번째로 마시는 포도주가 2번 연속이라면?

2번 연속이다라는건 N-1번째는 무조건 마신다는 뜻이다. 

그럼 n-2번째는 절대 마시면 안된다. 대신 n-3번째는 마시든 말든 상관없다.

이럴땐 dp[N] = dp[N-3] + arr[N-1] + arr[N] 

이 중 최댓값을 구하면 된다!

<풀이 소스>

이건 설명이 좀 약한듯한데.....

좀 더 쉬운 설명방법이 생각나면 수정하겠다...