문제 설명

개미전사는 메뚜기 마을의 식량창고를 약탈하려고 한다. 메뚜기 마을에는 여러개의 식량창고가 있고, 일직선으로 이어져 있다. 메뚜기 정찰병들은 서로 인접한 식량창고가 공격받으면 알 수 있기 때문에, 들키지 않고 식량창고를 약탈하기 위해서는 최소 1칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개와 각각의 창고에 들어있는 식량의 양이 주어졌을때 개미전사가 얻을 수 있는 식량의 최대값은?

문제 풀이

Top-down

점화식 1

i번째 칸에서 개미전사가 할 수 있는 선택은

1. 지금 칸 털기 -> i+2번째 칸부터 털 수 있음
2. 지금 칸 안털기 -> i+1부터 털 수 있음

이다. 두 경우중 더 많은 식량을 털 수 있는 경우를 선택해야 한다.

1. 상태 정의
   $a_i$ : i번째 창고부터 털 수 있는 최대 값
   $a_i = max(a_{i+2}+food_i, a_{i+1})$

2. 코드 작성

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

dp = [-1] * (N+1)

def get_food(x):
    if x >= N:
        return 0
    if dp[x] != -1:
        return dp[x]
    dp[x] = max(get_food(x+2)+food[x], get_food(x+1))
    return dp[x]
get_food(0)
print(dp[0])

처음에는 풀이의 점화식과 달라서 햇갈렸다. x번째 창고부터 털 수 있는 최대 값을 구하는 함수 get_food()에 0부터 넣지만 타고 타고 올라가면 dp 리스트에 N-1의 값부터 저장되므로 이 방법도 탑다운이 맞는 것 같다.

점화식 2

풀이의 점화식은 이것이다.

개미전사가

1. i-1번째 창고를 턴 경우에는 현재 창고를 털 수 없음
2. i-2번째 창고를 턴 경우에는 현재 창고를 털 수 있음

1. 상태 정의
   $a_i$ : i번째 창고까지 털 수 있는 최대 값
   $a_i = max(a_{i-2}+food_i, a_{i-1})$

2. 코드

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

dp = [-1] * (N+1)

def get_food(x):
    if x < 0:
        return 0
    if dp[x] != -1:
        return dp[x]
    dp[x] = max(get_food(x-2)+food[x], get_food(x-1))
    return dp[x]
get_food(N-1)
print(dp[N-1])

Bottom-up

1. 상태 정의
   $a_i$ : i번째 창고까지 털 수 있는 최대 값
   $a_i = max(a_{i-2}+food_i, a_{i-1})$

2. 코드

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

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

dp = [0]*100
dp[0] = storage[0]
dp[1] = max(dp[0], storage[1])

for i in range(2, N):
    dp[i] = max(dp[i-1], dp[i-2]+storage[i])

print(dp[N-1])