문제
- 메뚜기 마을의 식량 창고는 일직선으로 이어져 있다.
- 각 식량창고는 정해진 식량의 수를 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다.
- 개미 전사가 정찰병에게 틀키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다.
예시
예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하면,
{1,3,1,5}
개미 전사는 총 8 개의 식량을 빼앗을 수 있다.
입력
- 첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
- 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)
#개미전사
n = int(input())
array = [int(n) for n in input().split()]
#box에서 for문을 돌려서 최대값 두개를 찾아야함 - dp테이블 저장
#이웃은 안되므로 n+1이어야 함
#앞에서 계산한 결과를 저장하기 위한 dp table 초기화
d = [0]*100
#dynamic 프로그래밍 보텀업 진행
d[0] = array[0]
d[1] = max(array[0], array[1]) #max인걸 dp테이블 [1]에 저장
#d[2] 부터 n번째 항까지 반복
for i in range(2,n):
d[i] = max(d[i-1],d[i-2] + array[i])
print(d[i])
#결과 출력
print(d[n-1])
dp테이블의 개념이 잘 이해가지 않아서.. 헷갈렸다.
점화식을 세워 보면,
ai = i번째 식량창고까지 최적의 해(얻을 수 있는 식량의 최댓값)
ki = i번째 식량창고에 있는 식량의 양
ai = max(ai-1, ai-2, ki)
한 칸 떨어진 창고는 털지 못하므로, i-3번째 이하는 고려할 필요가 없어진다.
고려할 사항은 i-1, i-2+i번째 식량창고에 있는 식량의 개수
그래서,
테스트 케이스(여기서는 100) 만큼 dp테이블을 초기화 하고, dp테이블의 0번째 index에 입력받은 array의 첫번째 원소를 삽입한다.
array의 1번째 원소부터는 array의 0번째 원소와 비교해 큰 값을 dp테이블에 저장한다.
반복문을 통해 array의 n항까지 반복하며 dp테이블을 채운다.