개미 전사

출처:: 

분류:: 다이나믹 프로그래밍

 

1. 문제 이해 및 해결과정

 

 1) i-1번째 식량창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 없다.

 2) i-2번째 식량창고를 털기로 결정한 경우, 현재의 식량 창고를 털 수 있다.

 1번과 2번 중 더 큰 값을 선택하면 된다

 => a(i) = max(a(i-1),a(i-2)+k)

 

2. 풀이방법

 1. bottom-up

#개미 전사
#
import sys
sys.stdin = open("input.txt","r")

dp=[0]*101
n=int(input())
arr=list(map(int,input().split()))

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

print(dp[n-1])

3. 오답원인

 

4. 알게된 점