[이코테] 다이나믹프로그래밍 - 개미 전사

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을엔 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식랴창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량 창고 N개에 대한 정보가 주어질 때 얻을 수 있는 식량의 최댓값을 구하여라

입력조건

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

출력조건

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

사고과정

• DP 테이블에는 얻을 수 있는 식량의 최댓값을 하나씩 담아내는 것을 정확히 이해하지 못함. 단순히 DP 테이블에 식량 정보를 담아가는 것만 생각함. 그래서 N이 증가함에 따라 식량의 최댓값을 하나씩 저장하는 DP 테이블, 주어진 식량 정보 Array 2개 따로 운영하도록 해야 했음
• 입력 예시를 도식화한 후 왼쪽부터 해당 식량창고를 털을 때 최대일지 털지 않을 때 최고일지를 비교하면서 최대값을 DP 테이블에 저장하면 되었음. 털 경우에는 주어진 식량 정보 Array를 활용해 해당 식량 창고의 식량 개수를 얻을 수 있음.
• 어려움..

풀이

import sys

N = int(input())
array = list(map(int, input().split()))
# DP 테이블(얻을 수 있는 식량 최댓값을 저장해 나감)
d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])  # 두번째 칸을 털지 or 두번째 칸을 안털고 첫 번째 칸을 털지 비교

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

print(d[N-1])