[이코테] [5] 다이나믹 프로그래밍 ( 동적계획법 )

 

다이나믹 프로그래밍 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결합니다.

 

예제1) 피보나치 수열

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4))

 

메모리제이션 기법

- 한번 계산한 결과를 메모리 공간메 메모하는 기법
- 위의 피보나치 수열에 대입해 볼 때, 이미 계산된 함수를 생략할 수 있는 장점

 

 

예제2) 개미전사

- 개미 전사가 식량창고를 선택적으로 약탈하여 식량을 뺏을 때 가장 큰 식량을 얻을 수 있도록 해야합니다.

- 정찰병에게 들키지 않고 식량창고를 약탈하기 위해선 최소한 한칸 이상 떨어진 식량창고를 약탈해야 합니다.

- 예를 들어 [ 1, 3, 1, 5 ] 일 때 두번째와 네번째 창고를 약탈하는 것이 식량을 최대값을 얻을 수 있습니다.

- 입력 예시

   4

   1 3 1 5 

- 출력 예시 

   8

 

코드

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

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
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])

 

예제 실행 과정
예를 들어, array = [1, 3, 1, 5]인 경우를 생각해보면:
d[0] = 1: 첫 번째 창고의 식량 양
d[1] = max(1, 3) = 3: 두 번째 창고까지의 최대 식량 양
d[2] = max(3, 1 + 1) = 3: 세 번째 창고까지의 최대 식량 양
d[3] = max(3, 3 + 5) = 8: 네 번째 창고까지의 최대 식량 양