[백준 2156 포도주 시식 문제] PYTHON

 

이번 문제는 전에 포스팅한 2579 계단 오르기 문제와 거의 같다.

기존의 코드에 추가된 요소를 몇개 추가했다.

첫번째로 생각해야하는것은 마지막 잔을 전과 달리 마시지 않아도 된다.

두번째로는 꼭 마시지않은 후에는 마셔야할 의무가 없다. 

 

 

harry595.tistory.com/190

[백준 2579 계단 오르기 문제] PYTHON

 

다음과 같이 코드를 짤 수 있다.

N = int(input())
cost= []
dp = [0 for i in range(N)]
for _ in range(N):
    cost.append(int(input()))
if(N==1):
    print(cost[0])
elif(N==2):
    print(cost[0]+cost[1])
elif(N==3):
    print(max(cost[0]+cost[2],cost[1]+cost[2],cost[0]+cost[1]))
else:
    dp[0]=cost[0]
    dp[1]=cost[0]+cost[1]
    dp[2]=max(cost[0]+cost[2],cost[1]+cost[2],cost[0]+cost[1])
    for i in range(3,N):
        dp[i]=max(dp[i-1],dp[i-3]+cost[i]+cost[i-1],dp[i-2]+cost[i])
    print(dp[N-1])