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

'이것이 코딩 테스트다' 책에 수록 되어 있는 실전 문제이다. 문제의 자세한 내용은 책을 참고하도록 하자.

 

책에서 나오는 점화식은 문제 설명을 해주며 결국 아래와 같은 점화식을 만든다.

$$a_i = max(a_{i-1}, a_{i-2}+k_i)$$

 

하지만 나는 다른 방법으로 점화식을 찾았다. 하지만 이 점화식이 옳은 점화식인지 확인이 어렵다는 것이다.

$$d_i = k_i + max(d_{i-2}, d_{i-3}), (i>3)$$

*단, $d_1 = k_1$,    $d_2 = k_2$,    $d_3 = k_3 + d_1$ 이다.

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

dp = [0] * N
dp[:2] = K[:2]

ans = 0
for i in range(2, N):
    dp[i] = (d:=K[i] + max(dp[i-2], dp[i-3]))
    ans = max(d, ans)

print(ans)