문제
일직선으로 이어져 있는 식량 창고를 공격하여 한다. 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 선택적으로 약탈하여 식량을 빼앗을 에정이다.
서로 인접한 식량창고는 공격할 수 없다.
조건
입력 조건
1. 첫째 줄에 식량 창고의 개수가 주어진다.
2. 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량 개수가 주어진다.
출력 조건
1. 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라.
코드
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])풀이
다이나믹 프로그래밍의 핵심은 어떻게 점화식을 세우는가? 인 것 같다.
그리고 본 문제에서 점화식을 세우는 기준은 본인을 포함하여 인접하지 않은 값들을 더하는 게 큰지, 본인 바로 앞까지 값들의 합이 큰지 비교하는 것이다.
최댓값을 구하는 것이므로 애초에 전부 더한 값을 비교하면 된다고 생각했다. 또한 누적합이기 때문에 다이나믹 리스트의 맨 끝 값이 최댓값이 된다.
기준을 통해 점화식을 세웠다면 구현은 쉽다. 바텀업인 경우 다이나믹 리스트의 초기값을 설정해주고, 반복문을 통해 채워 넣어주면 된다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
