[다이나믹 프로그래밍] 개미 전사 (실전문제, 이것이 코딩테스트다 with 파이썬)

다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법)

메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

문제

 

해설

문제의 점화식

• (i - 1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 X
• (i - 2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 O

* 왼쪽부터 (i - 3)번째 이하의 식량창고는 고려할 필요 X → 한 칸 이상 떨어진 식량창고는 항상 털 수 있음

즉, 왼쪽부터 순차적으로 최댓값을 업데이트 해오면, d[끝]에 다다랐을 때 해당 창고까지의 최댓값으로 업데이트 되어 있음

* 점화식에서는 첫째항을 잘 신경 써 주자

 

풀이

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

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

# 다이나믹 프로그래밍 진행(보텀업)
# 계수 0부터 시작(인덱스)
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])

 

해석

변수 : N 창고 개수, array 식량 정보, d 보텀업에서 DP테이블

 

1. 창고 개수 N 입력받기

2. 창고 별 식량 정보 array 입력받기

3. DP테이블 초기화 : [0] * 100

-------- 다이나믹 프로그래밍 : DP 테이블에서의 최댓값 --------

ㄴ 현재의 수 i

ㄴ 2 ~ x 까지의 반복문 수행

4. 첫째 항

ㄴ d[0]의 현재까지 최댓값 = 식량정보 array[0]

ㄴ d[1]의 현재까지 최댓값 = max(array[0], array[1])

* 일반항에 대해 (i -1)과 (i - 2)을 수행할 수 없는 경우 정의

5. 일반항 : 각 경우에 따른 최댓값으로 업데이트

ㄴ d[i] = max(d[i - 1], d[i - 2] + array[i])    # 최댓값(붙어있는 항 하나 or 나와 곧바로 떨어진 항의 합)

---------------------------------------------------------------------------------

6. 최소값으로 자동 업데이트되어 d[x] 출력