다이나믹 프로그래밍: 개미 전사

리스트에 값이 들어있는데, 몇 개의 칸을 선택해서 선택한 칸들의 값의 합을 최대로 만들어야한다.

조건: 칸을 선택할 때 인접한 칸을 선택할 수 없다

 

 

x=int(input())
k=list(map(int,input().split()))
d=[0]*3001
d[0]=k[1] #1번창고까지의 최대 식량
d[1]=max(k[1],k[2]) #2번창고까지의 최대 식량
for i in range(2,x):
    d[i]=max(d[i-1],d[i-2]+k[i]) #이전것까지의 식량 vs 전전것+이번것까지 식량

print(d[x-1])

 

식량창고의 개수가 x

각 식량창고에 있는 식량의 크기를 저장할 리스트 k=[]

n번째 식량창고까지 있다고 가정했을 때 최대로 훔칠 수 있는 식량의 양=d[n]

 

d[i]= max(d[n-1], d[n-2]+k[i])

 

 

.

.

.

...

처음알았다