[DP] 다이나믹 프로그래밍 (3) 실전 문제 - 개미 전사 ⭐

이코테  p.220 실전 문제 - 개미 전사

입력 예시

4 1 3 1 5

출력 예시

8

교재 소스코드

• 왼쪽 식량 창고부터 차례대로 털지 안 털지를 결정하는데, 특정한 i번째 식량 창고를 털지 안 털지를 결정하는 경우의 수는 2가지 존재
  1. (i - 1)번째 식량 창고를 턴다면 현재 식량 창고는 털 수 없음
  2. (i - 2)번째 식량 창고를 턴다면 현재 식량 창고를 털 수 있음
  3. 참고로 (i - 3)번째 이하의 식량 창고는 항상 털 수 있기 때문에 고려할 필요 없음
• 따라서 이 두가지 중에서 더 많은 식량을 털 수 있는 경우 선택
• 구체적인 과정 예시: n = 4, 리스트는 [1, 3, 1, 5]로 주어졌을 때, 왼쪽부터 턴다고 가정
  
  1. 첫 번째 식량 창고에서 털 수 있는 최대 식량은 1
  2. 두 번째 식량 창고에서 털 수 있는 최대 식량은 3
  3. 세 번째 식량 창고에서 털 수 있는 최대 식량은 max(3, 1 + 1) = 2
  4. 네 번째 식량 창고에서 털 수 있는 최대 식량은 max(2, 3 + 5) = 8
  5. 따라서 털 수 있는 식량의 최댓값은 8
• 점화식으로 나타내면
  • K를 i번째 식량창고의 식량 개수라고 할 때 
  • a(i) = max(a(i - 1), a(i - 2) + K)

# 입력받기
n = int(input())
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 100

# 다이나믹 프로그래밍 진행 (바텀업 방식)
dp[0] = array[0]
dp[1] = max(array[0], array[1])
for i in range(2, n):
  dp[i] = max(dp[i - 1], dp[i - 2] + array[i])

print(dp[n - 1])