[DP] 8 - 3 개미 전사

정해진 수의 식량을 저장한 식량창고에서 개미 전사는 선택적으로 약탈하여 식량을 빼앗는다. 정찰병에게 들키지 않고 약탈하기 위해서 는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

예를 들어 {1, 3, 1, 5} 의 식량 창고가 있을 때 개미 전사는 두번째, 네번째 식량창고를 선택했을 때 최댓값인 8개의 식량을 빼앗을 수 있다.

 

식량창고 N개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최댓값을 구하는 프로그랭램을 작성하시오

 

입력 조건

• 첫째 줄은 식량창고의 개수 N이 주어진다. (3<=N<=100)
• 둘째 줄은 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

 

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오

---

현재 위치가 i일 때, i-1 창고를 털면 i를 털 수 없고, i-2를 털면 i를 털 수 있다. 

 

 

# 정수 N를 입력받기
n = int(input())

# 모든 식량 정보 입력받기
array = list(map(int, input().split()))

# 앞서 계산한 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 보텀업
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
    d[i] = max(d[i-1], d[i-2] + array[i])

print(d[n-1])