문제설명

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. (...) 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

접근

일직선으로 이어져 있다
최소한 한 칸 이상 떨어진
한 시점에 고려하는 식량창고(현재 식량창고)에 대해 그 식량창고를 공격한 경우와 그렇지 못하는 경우로 나누어서 생각할 수 있음

• (i-1)번째 식량창고를 공격한 경우 (현재 식량창고를 공격할 수 없는 경우)
• (i-2)번째 식량창고를 공격한 경우 (현재 식량창고를 공격할 수 있는 경우)

점화식
a_i = max(a_i-1, a_i-2 + ki)

i번째 식량창고에 대해 위 경우를 고려하는 경우, i-1번째까지의 최적의 해와 i-2번째까지의 최적의 해 + i번째의 값 중 최댓값이 i번째의 최적의 해로서 결과 저장용 리스트(이하 d) i-1번째 원소(리스트 인덱스는 0부터 시작됨을 고려)가 될 것이다. i번째의 식량창고에 대한 최적의 해를 계산할 때, 이전에 계산되어 d에 저장된 i-1번째의 그것과 i-2번째의 그것을 가져다 쓴다. 이는 다이나믹 프로그래밍 기법 중 하나인 보텀업 방식으로 구현한 것으로, 이전에 계산된 작은 문제의 해를 기반으로 큰 문제의 해를 순차적으로 도출한다.

풀이

n = int(input())
array = list(map(int, input().split())

// 결과 저장용 리스트 초기화
d = [0] * 100 

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

배운점

조건에 대한 경우의 수를 고려할 때, 긍정의 경우와 부정의 경우 두가지로 나누어 생각할 수 있다.
다이나믹 프로그래밍의 보텀업 방식 사용시, 최종적인 최적의 해는 그 전에 이미 구한 부분의 최적의 해로 구하기 때문에 그 순간의 조건에 따른 경우의 수만 고려하면 된다. => 점화식을 구상할 필요가 있다.