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

로직

1. N 식량창고 개수를 입력받는다
2. K 식량창고에 저장된 식량개수 리스트를 입력받는다
3. d[0] = K[0]
   d[1] = K[0]이랑 K[1]중에 큰 애로 간다 -> max()
4. for i in range(2,N) :
5. d[i] = max(d[i-1], d[i-2]+K[i]) : 점화식

코드

N = int(input())
K = list(map(int,input().split()))
d = [0] * 100

d[0] = K[0]
d[1] = max(K[0],K[1])

for i in range(N) :
  d[i] = max(d[i-1], d[i-2]+K[i])

print(d[N-1])

주의사항

• d[1] 에서 얻을 수 있는 식량의 최대 값은 K[0]과 K[1] 의 값 중 큰 값이다
  -> max() 사용
• 점화식 : d[i] = max(d[i-1], d[i-2]+K[i])
  -> i-1 까지 얻은 최적의 식량 값과
  -> i-2까지 얻은애 + K[i] 현재 위치에 대한 식량값
  => 둘중에 큰 애로 고고
• 결과를 출력 할 때는 d[N-1]을 출력해준다
  -> N까지 식량창고가 있기 때문 (0~N-1)