[이.취.코] Chap 8. 다이나믹 프로그래밍 - 개미전사2021년 8월 26일 9:46 오전3분주어진 일직선 상의 식량창고들 중 서로 인접한 식량창고가 공격받으면 들키기 때문에 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 하는 개미 전사가 얻을 수 있는 식량의 최댓값을 구하는 문제이다. 다이나믹 프로그래밍으로 해결할 수 있으며, 점화식은 (i-1)번째 식량창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 없다. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다는 것이다.
