개미전사(p.220) - 다이나믹 프로그래밍(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명

 

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. 

 

{1, 3, 1, 5}

 

1

3

1

5

 

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오. 

 

입력 조건 

 

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3 <= N <= 100) 
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000) 

 

출력 조건

 

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오. 

 

입력 예시 

 

4
1 3 1 5

 

출력 예시 

 

8

 

 

---

 

해설 

 

1로 만들기와 비슷한 다이내믹 프로그래밍 문제다. 격자로 식량창고를 털 수 있다고 했으니까 i를 기준으로 i - 1과 i - 2를 고려해서 점화식을 만들 수 있다. 해설에서 주어진 점화식은 다음과 같다. 

 

a_i = max(a_i-1, a_i-2 + k_i) 

 

(k_i = i번째 식량창고에 있는 식량의 양) 

 

해설에서 제공하는 코드는 다음과 같다. 

 

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

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

# 다이나믹 프로그래밍 진행(보텀업) 
d[0] = array[0] 
d[1] = array[1]
for i in range(2, n):
    d[i] = max(d[i], d[i - 2] + array[i]) 

# 계산된 결과 출력
print(d[n - 1]) 

# i를 탐색할때 i - 3이하는 탐색할 필요 없다.
# 왜냐하면 인덱스 0, 1이 지정이 되어 있는 상태에서 2부터 반복문을 돌리는데 2를 돌릴때 0, 1이 탐색되고
# 3을 돌릴때 1, 2가 탐색되고 마지막 n-1까지 가서 멈추기 때문에 상관없다. 
# 바텀업 방식이라서 i번째를 탐색할때 i - 1, i - 2를 다루게 되는데 i - 1, i - 2에는 이미 이전 값들중 최대값이 포함되어있다.

 

3번째 줄에서 d = [0] * 100 으로 입력했는데 101이 아닌 100으로 맞춰준 이유는 array의 인덱스와 맞춰주기 위해서다.

 

d[i]는 지금까지 결과의 누적합이란 것과 최소한 한칸 이상 떨어져서 식량을 털어야 하므로 i기준 i -2까지 고려해야 한다.

 

해설에선 d[1]을 d[1] = max(array[0], array[1]) 으로 점화식으로 표현했지만 d[1] = array[1]로 해도 됐을 법 싶다. 이유는 예시에서 알 수 있는데 n= 3 일 때 입력 값은 1, 3, 1이니까 침투해서 얻을 수 있는 가장 큰 값은 3이다. n의 최솟값이 3이라 print(d[3-1])하면 ①, ②, ③ 숫자에서 ②가 ①과 같으면 무조건 ① + ③만 나오게 된다. 

하지만, 어차피 2개를 더한 쪽이 더 클 수밖에 없기 때문이다.