[python] 개미 전사 (다이나믹 프로그래밍)

- 식량을 억기 위해 최소 한 칸 이상 떨어진 식량 창고 약탈

- 얻을 수 있는 식량의 최댓값

 

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])