다이나믹 프로그래밍 (Dynamic Programming) (3) - 실전문제 8.3) 개미 전사

문제)

N개의 식량 창고에 대한 정보를 입력받는다. 이 때 입력받은 순서대로 식량 창고가 인접해 있다고 생각한다. 개미 전사는 일직선 상에 존재하는 식량 창고 중에서 서로 인접하지 않은, 즉 최소한 한 칸 이상 떨어진 식량 창고들을 약탈할 수 있다. 이 때 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입력조건)

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3 <= N <= 100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

출력조건)

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

입력예시)

4

1 3 1 5

출력예시)

8

---

풀이)

이 문제 또한 앞의 실전 문제와 동일하게 바텀업 방식으로 간단하게 해결할 수 있다. 바텀업 방식의 핵심인 결과 리스트를 생성하고 모든 값을 0으로 초기화한다. 이 후 입력받은 N개의 식량 창고에 대한 정보를 반복문을 통해 첫번째 인덱스부터 확인하며 결과 리스트에 값을 채울 것이다. 이 때 중요한 제한이 인접하지 않은 식량 창고를 침략해야 한다는 것이기 때문에 두 가지 경우가 생기게 된다. 

1. 반복문의 (현재 인덱스-1) 을 침략한 경우 => 현재 인덱스는 침략할 수 없다. => 결과 리스트[i-1]
2. 반복문의 (현재 인덱스-2) 를 침략한 경우 => 현재 인덱스를 침략할 수 있다. => 결과 리스트[i-2] + 입력 리스트[i]

위의 두 가지 경우의 최댓값을 결과 리스트의 현재 리스트에 저장하면서 결과 리스트를 채워 나가면 문제를 해결할 수 있다. 최종적으로 입력받은 N 번째 인덱스의 값이 원하는 문제의 답이 된다.