개미 전사 [dp]

# 전에 획득한 식량에 현재 식량 더함 -> DP

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

for i in range(2,len(array)):
    array[i]=max(array[i-2]+array[i],array[i-1])
    
print(max(array))

• n−1 에서의 식량 최대값(an을 더할 수 없는 이유: 바로 옆의 식량) 과 n−2의 식량 최대값에서 an 을 더한 값의 최대값을 비교하면 됨

다른 풀이

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

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

print(d[n-1])

• dp로 리스트 하나 더 선언