[백준, 2156번] 포도주 시식

초기에 생각한 로직으로는 아래와 조금 차이가 있었는데

• 우선 가장 중요했던 dp에 추가하며 누적합을 시키는 대상 선정으로 
• 현재가 i 라고 했을 때 li[i]+li[-2]+dp[i-3] 와 li[i]+dp[i-2] 중 가장 큰 값만을 출력하도록 했었는데
• 다른 반례들을 찾아보았을 때 
  • 6개 포도주가 있을 경우 1,1,0,0,1,1 의 경우에는 위의 로직으로 셈을 한다면 3이라는 결과가 나오게 된다.
• 그래서 li[i]+li[-2]+dp[i-4] 를 한 값과도 비교를 해서 더 넓은 범위의 조사를 할 수도 있다는 것을 이해하게 됨
• 또한 기존 dp의 값으로는 dp[0] = li[0] 으로만 넣고 풀었는데 
• 위에 추가한 로직으로 인해 dp[2] 값까지 추가를 해줘야 하게 되었고
• dp[3] 의 값은 내가 생각하기로 경우론 1+2, 1+3, 2+3으로 생각해서 조합을 이용해 큰 값을 넣어주며 해결.  

import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
li = [int(input()) for _ in range(n)]
if n <= 2: print(sum(li))
else:
    dp = [0]*n
    dp[0], dp[1], dp[2] = li[0], li[0]+li[1], sum(max(combinations(li[:3],2)) )
    for i in range(3, n): dp[i] = max(li[i]+li[i-1]+dp[i-3], li[i]+li[i-1]+dp[i-4], li[i]+dp[i-2])
    print(max(dp))