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

문제

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

 

예시

[1, 3, 1, 5]

 

개미전사는 두번째 식량창고와 네번째 식량창고를 선택했을때 최대값인 8개의 식량을 빼앗을 수 있다.

 

 

 

나의 코드

list = [1, 3, 1, 5]

odd_sum = 0
even_sum = 0

for i, value in enumerate(list):
    if i % 2 == 0:
        even_sum += value
    else:
        odd_sum += value


print(max(even_sum, odd_sum))

 

해당 코드는 다이나믹 프로그래밍의 풀이법이라고 하기엔 한참 부족하다. 단순히 짝수 원소의 총 합과 홀수 원소들의 총 합을 구해서 max 함수로 최대값을 추출해내는 방법은 문제 출제자가 원하고자하는 정답 코드가 아닐 것이다.

 

 

 

정답 코드

# 정수 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])

출처: github.com/ndb796/python-for-coding-test/blob/master/8/6.py

 

 

 

문제풀이

(1) 설명

d = [0] * 100

 

우선 해당 문제를 해결하려면 우리가 결과적으로 얻어야하는 값은 짝수번째의 총 합과 홀수번째의 총 합 중 최대값을 알아내야한다는 것이다. dp 테이블을 생성해준다.

 

d = [0, 0, 0, 0, 0, 0, 0, ....]

 

 

(2) 설명

d[0] = array[0]
d[1] = max(array[0], array[1]) 

 

우리는 홀수끼리, 짝수끼리 비교를 해야하므로 처음 0번째 인덱스와 1번째 인덱스는 미리 저장을 한다. 이렇게 d[1]에도 첫번째 원소와 두번째 원소를 비교하여 최대값이 들어가게된다. 만약 입력된 리스트의 길이가 2일 경우에도 정답(최대값)을 추출할 수 있다.

 

 

(3) 설명

for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

 

해당 문제의 가장 핵심적인 로직이다. 이해를 쉽게 하기 위해서, i가 2일때, 3일때, 4일때를 우선 차근차근 파악해보자.

 

예시로 array = [2, 5, 7, 9, 1, 6] 일때를 보자.

 

i = 2의 경우

d[2] = max(d[1], d[0] + array[2])   # max(5, 9) = 9

=> d[1] : i - 1까지의 최대값 (홀수번째들의 합)

=> d[0] + array[2] : i - 2까지의 최대값 + 현재 i번째의 값 (짝수번째들의 합)

=> 짝수번째들의 합이 크므로 d[2] = 9

 

i = 3의 경우

d[3] = max(d[2], d[1] + array[3])  # max(9, 14) = 14

=> d[2] : i - 1까지의 최대값 (짝수번째들의 합)

=> d[1] + array[3] : i - 2까지의 최대값 + 현재 i번째의 값 (홀수번째들의 합)

=> 짝수번째들의 합이 크므로 d[3] =  14

 

i = 4의 경우

d[4] = max(d[3], d[2] + array[4])  # max(14, 10) = 14

=> d[3] : i - 1까지의 최대값 (홀수번째들의 합)

=> d[2] + array[4] : i - 2까지의 최대값 + 현재 i번째의 값 (짝수번째들의 합)

=> 홀수번째들의 합이 크므로 d[4] = 14

 

위 코드를 보면 공통적인 요소를 깨닫게된다. 우선 i가 짝수일 경우(i=2, i=4)를 보면 현재까지 더한 홀수의 값과 현재까지 더한 짝수의 값에 현재 인덱스의 값을 더한 값을 비교하여 max 값을 저장하고있다.

 

i번째 이전까지의 더한 홀수번째 값 vs i번째 이전까지 더한 짝수번째 값 + i번째 값

 

 

(4) 설명

 

결론적으로 i가 짝수일경우 앞에서 홀수번째들의 합이 최대값이였더라도, 현재 i번째의 값을 더함으로써 짝수번째들의 합이 커진다면 해당 d[i]에는 짝수번째들의 합이 들어간다. 또한 동일하게 i가 홀수일경우 앞에서 짝수번째들의 합이 최대값이였더라도, 현재 i번째의 값을 더함으로써 홀수번째들의 합이 커진다면 d[i]에는 홀수번째들의 합이 들어간다. 결국 array 리스트의 마지막 값의 차례일 경우에는 홀수번째들의 합과 짝수번째들의 합 중 최대값이 들어가기 때문에,

 

print(d[n - 1])

 

d[n-1] 값으로 결과를 출력할 수 있다.