2156 포도주 시식

포도주가 일렬로 놓여있고, 각 포도주마다 가중치가 있다. 연속된 세개의 포도주를 고를 수는 없다고 할 때, 가중치의 합의 최대를 고르는 문제이다.

DP로 해결이 가능하다. 여기서 DP는 i번째까지 골랐을 때 가중치의 합의 최대값을 나타낸다. 비교는 i번째의 두칸 전 DP와 세칸전 DP + 한칸 전 포도주 중 큰 값을 고르면 된다.

소스