[Algorithm] Dynamic Programming - ‘개미 전사 문제’

📣 학습한 내용을 정리한 글입니다.

다이나믹 프로그래밍 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.
메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져있다.
각 식량창고에는 정해진 수의 식량을 저장하고 있으며, 개미전사는 식량창고를 선택적으로 빼앗을 예정이다.
개미정사가 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다.
식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 식량창고 N의 개수가 주어진다. (3 <= N <= 100)
두 번째 줄에는 공백을 기준으로 각 식량창고에 저장된 식랴으이 개수 K가 주어진다.(0 <= K <= 1,000)

출력

첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

문제 풀이

---

Dyanmic Programming Algorithm 참고내용

• 동적계획법이라고도 부르며, 최적 부분구조 및 중복되는 부분 문제의 조건에 맞게 출제된다.
  
• 통상적으로 점화식을 이용하며 bottom-up(상향식)방식으로 풀 수 있다.
  
• dp 테이블을 이용하여 점화식을 적용시켜 문제를 풀어간다.
  

위 참고사항을 준수하며, 풀어보자.
dp 테이블을 만들어 N개일 때 최대의 식량을 얻을 수 있는 배열을 만든다.
점화식으로 dp[i] = max(dp[i-1], dp[i-2] + k[i])가 나온다.

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 영상

---