[이코테 실전문제] 개미전사 - python

개미 전사

문제

일직선으로 이어진 식량 창고에서 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야한다. 식량 창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오

제한사항

• 3 <= N <= 100
• 0 <= K <= 1000

풀이

문제의 목표는 최대한 많은 식량 선택하기

작은 문제 정의하기

어떤 칸을 선택했을 때 얻을 수 있는 식량의 최댓값

0번째 칸까지 중에 선택했을 때 얻을 수 있는 식량의 최댓값?

1번째 칸까지 중에 선택했을 때 얻을 수 있는 식량의 최댓값?

2번째 칸까지 중에 선택했을 때 얻을 수 있는 식량의 최댓값?

3번째 칸까지 중에 선택했을 때 얻을 수 있는 식량의 최댓값?

작은 문제로 큰 문제 해결할 수 있는지 확인하기

왼쪽부터 차례로 선택한다고 했을 때 해당 순서의 창고를 선택할 수도 있고 안 할 수도 있다.

dp [i] = max(dp[i - 1] + dp[i - 2] + arr[i])

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])
​
for i in range(2, n):
  dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])
print(dp[n - 1])