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

N 개의 숫자가 입력 될때 최소 한칸 이상씩은 간격을 두고 선택할 때  선택한 숫자의 합의 최댓값을 구하라.

 

 

입력 예시)

4

1 3 1 5

 출력예시)

8

 

 

나의 코드

N=int(input())
arr=list(map(int,input().split()))

arr.append(0)
dy=[0]*(N+1)
dy[1]=1
dy[2]=max(arr[0],arr[1])
for i in range(3,N+1):
    dy[i]=max(dy[i-1],max(dy[:i-1])+arr[i-1])

print(dy[4])

음..그림을 그려가며 생각한 로직대로 짜서 입력값대로의 출력값은 나오긴 했는데  확신이 없다..

dp테이블은 한칸을 건너뛰어야 하니 '바로 이전 테이블 값'과 ' 두칸 이전 까지의 dp테이블 값의 최대값과 현재 arr의 i(인덱스)의 합 중 더 큰값으로 구성하였다.

 

정답 코드

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])

음 그래도 나의 흐름과 거의 비슷하다..!

우선 점화식은 첫번 째 (i-1)번째 식량을 털경우와 두번 째 i-2번째 식량 창고를 털기로 결정한 경우 현재 식량 창고를 털수 있다

이다. 따라서 둘중 최대값을 택해 dP 테이블을 갱신 시키면 된다.

 

나의 코드와 단 하나의 차이점이자 아직도 이해가 안되는 것은 i-2번쨰 식량 창고를 털기로 결정한 경우는 이다.

난 d[i-2]가  아닌 d[0]~d[i-2] 중 최대값에 array[i]를 더해야 한다고 생각하는데..흠

dp테이블은 늘 쭉 커진다고 확정할 수 있을까..?..

 

조금더 다아나믹 프로그래밍적 사고가 발달하면 다시 고민해 봐야겠다..