소피it블로그

문제, 풀이 출처: https://youtu.be/5Lu34WIx2Us 이 문제 역시 1) 최적의 부분 구조와 2) 중복되는 부분 문제라는 조건을 만족시키기 때문에 다이나믹 프로그래밍으로 접근하여 풀 수 있다. 핵심은, 한 칸 이상씩 떨어진 식량 창고를 털어야 하기 때문에 마지막 n번째 식량 창고에 대하여 1) i - 1 번째 식량 창고까지의 최적의 해 2) i - 2 번째 식량 창고까지의 최적의 해 + i번째 식량 창고에 저장된 식량 둘 중 더 큰 값을 선택하면 된다는 것. 그리고 각각은 부분 문제로 반복된다는 점을 파악하는 게 중요하다. i번째 창고까지의 최적의 해를 Ai라고 하고, i번째 창고에 있는 식량의 양을 Ki라고 한다면 다음과 같은 점화식이 성립한다. Ai = max(Ai-1, Ai-2 +..