[이.취.코] 개미 전사 - DP

- 이것이 취업을 위한 코딩테스트다

 

개미전사는 창고에서 식량을 턴다

바로 인접한 창고의 식량을 털면 발각될 수 있다

항상 1칸 떨어진 창고의 식량을 털어야 한다

털 수 있는 식량의 최댓값을 구해라

 

n = int(input())
food = list(map(int,input().split()))

dp = [0]*(n+1)
dp[0]=food[0]
dp[1]=max(food[0],food[1])
for i in range(2,n):
    dp[i] = max(dp[i], dp[i-2]+food[i])
print(dp[n-1])

 

처음에 dp[1]을 food[1]로 초기화했는데,

food[1]만 고려하면 안된다

0번 창고만 터는 경우, 1번 창고만 터는 경우 중 최댓값을 구해야 이후 솔루션들에서 제대로 최댓값을 구할 수 있다

 

입력예시

4

1 3 1 5

출력예시

8