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

1. 내 풀이

n = int(input())
k = list(map(int, input().split()))
dp = [0]*1002
result = 0

for j in range(n):
  dp[j] = k[j]

for i in range(3, n+2):
  dp[i] = max((dp[i] + dp[i-2]), (dp[i] + dp[i-3]))
  print(dp)

print(max(dp[n-2], dp[n-1]))

 

1-1. 풀이 도중 생각

1) 점화식을 차근차근 생각해보자

2) 결국 a_{n+2}와 a_{n+3} 값 중 최대가 되는 식을 선택해가면 될 것 같다

3) 처음엔 dp 테이블과 k 를 둘 다 사용하는 방식으로 코드를 짰는데, 그러면 값이 누적합산이 안 되어 k를 버리고 dp 테이블만 이용

 

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])

접근방법 자체는 비슷한 것 같은데 왜 max(d[i-1]+array[i], d[i-2]+array[i]) 가 아닌지가 궁금하다...

 

3. 새롭게 알게 된 것 or 새삼 다시 알게 된 것

1) 진짜... 점화식을 잘 찾아보고

2) 유형 자체를 익혀야 할듯