[dp/백준] 2156번: 포도주 시식

-문제:https://www.acmicpc.net/problem/2156

 

이전에 풀었던 계단 올라가기와 동일한 문제인데 다른점은 꼭 마지막 와인을 마시지 않아도 된다는 것. 

그래서 점화식에 추가할 것이 있다. 현재 와인을 마시지 않았을 조건(dp[i-1])

이에 대한 자세한 설명은 여기서 볼 수 있다.

https://www.acmicpc.net/board/view/60664

dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])

 

이 외에는 계단 올라가기와 동일하다. 

그동안 IndexError가 발생했던 이유가, n에 따라 data와 dp 리스트를 생성하면

n==1, n==2일 때는 숫자가 모자라서 for문을 못 돌린다. 그래서 조건에 따라 if, elif문을 작성하면 된다 

n=int(input())
data=[]
for _ in range(n):
    data.append(int(input()))
if n==1:
    print(data[0])
elif n==2:
    print(data[0]+data[1])
else:    
    dp=[0]*n
    dp[0]=data[0]
    dp[1]=data[1]+data[0]
    dp[2]=max(data[2]+data[0],data[2]+data[1],dp[1]) #dp[2]=dp[1]은 2번째 와인을 마시지 않았다는 말
    for i in range(3,n):
        dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])
    
    print(max(dp))