[백준] 포도주 시식

출처::  www.acmicpc.net/problem/2156

분류:: dp

 

1. 문제 이해 및 해결과정

6 10 13 9 8 1 a. 선택하는 경우  b. 선택하지 않는 경우 ooxo ooxx oxoox xxo 1. 연속된 2개를 선택하는 경우, i-3선택하고 i-2는 선택안하므로 초기화 , i-1선택, i선택  dp[i]=dp[i-3]+arr[i-1]+arr[i] 2. 1개를 선택하는 경우, i-2선택하고 i-1선택안하므로 초기화 i선택  dp[i]= dp[i-2]+arr[i] 3. 0개를 선택하는 경우  dp[i]=dp[i-1]

 

2. 풀이방법

 1. [python] dp

#포도주 시식
#https://www.acmicpc.net/problem/2156
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=[int(input()) for _ in range(n)]
dp=[0]*n

dp[0]=arr[0]
if n>=2:
    dp[1]=dp[0]+arr[1]
if n>=3:
    for i in range(2,n):
        dp[i]=max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i],dp[i-1])

# print(dp)
print(max(dp))

 

3. 오답원인

 

4. 알게된 점