[BOJ] (DP) 2156번 포도주 시식

다이나믹 프로그래밍 문제는 볼때마다 새롭다

 

3개의 요소를 연속으로 선택하면 안된다.

즉, i번째 요소는 연속으로 3번째인 요소가 되면 안된다.

i번째 요소가 0번째, 1번째, 2번째 일 때를 나누어서 다이나믹 프로그래밍을 하면 된다.

 

i번째 요소가 0번째 일경우 그 요소는 선택하지 않는다는 뜻이므로 dp[i-1]과 같음

1번째일경우 직전 요소는 선택하지 않았다는 뜻이므로 dp[i-2]+arr[i]

2번째일경우 직전요소를 선택하고, 그 이전의 요소는 선택하지 않았으므로 dp[i-3] + arr[i-1] + arr[i]

 

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = [0] + [int(input()) for _ in range(n)]
    if n==1:
        return arr[n]
    if n==2:
        return sum(arr)
    
    dp = [0] * (n+1)
    dp[1] = arr[1]
    dp[2] = arr[1]+arr[2]
    
    for i in range(3, n+1):
        dp[i] = max(dp[i-1], dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])
        
    return dp[n]

print(solve())

 

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식