백준 2156 - 포도주 [dp]

num = int(input())
arr= [int(input()) for _ in range(num)]
dp = [False for _ in range(num)]
if num == 1 :
    print(arr[0])
else :
    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    for i in range(2, num) :
        dp[i] = max(dp[i - 2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
        dp[i] = max(dp[i], dp[i-1])

    print(dp[-1])

하나 건너뛰면서 선택하던 기본 dp 문제들에서 한단계 업그레이드 된 문제.

 

해결 아이디어

1) 현재의 상황에서 생각하기

2) 만약 현재 선택이 건너뛰고 첫 선택이라면    dp[i-2] + arr[i]

3) 만약 이전꺼 선택하고 연속해서 선택중이라면 dp[i-3] + arr[i-1] + arr[i]

4) dp에는 각 스탭의 최댓값이 들어있어야 하므로 dp[i] = max(dp[i], dp[i-1])