[Dynamic Programming]개미 전사

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상 존재하는 식량창고 중 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 한다.

입력

4
1 3 1 5

출력

8

입력 조건 :  첫째 줄에 식량창고의 개수 N, 둘째 줄에는 공백으로 구분, 각 식량창고에 저장된 식량의 개수 K

출력 조건 : 개미 전사가 얻을 수 있는 식량의 최댓값 출력

 

나의 풀이

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

d = [0]*100

d[1] = k[0]
d[2] = max(k[0], k[1])

for i in range(3,n+1):
    d[i] = max(d[i-2] + k[i-1], d[i-1])

print(d[n])

바텀업 방식으로 다이내믹 프로그래밍을 구현하였다.

 

[고려해야 할 조건]

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

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

 

(1)과 (2) 중 더 많은 식량을 털 수 있는 경우를 선택하면 된다.