[DP 문제풀이] - 창고 털기

창고 털기 문제

N개의 창고가 있을 때, 얻을 수 있는 식량의 최댓값을 계산해 보자.
이때, 최소한 한 칸 이상 떨어진 창고들만 선택하여 털 수 있다.
예시) 창고1 1️⃣, 창고2 3️⃣, 창고3, 1️⃣, 창고4 5️⃣
현재 예시에서는 두번째 창고와 네 번째 창고를 선텍했을 때 최댓값인 8을 얻을 수 있다.

• 각 최적의 해를 수열에서의 각 항으로 보자. 어떤 특성이 있는지 확인할 수 있다.

f(5) = max(f(4), f(3) + arr(5))
f(3) = 위치 3까지의 해
f(4) = 위치 4까지의 해

• 4번째 f(4)를 털었다면, 5번째는 털 수 없다.
• 3번째 f(3)까지 고려했다면, 5번째는 털 수 있다.

이 문제도 두 조건에 만족한다.
1. 최적 부분 구조

• 큰 문제는 동일한 구조의 작은 문제의 조합으로 해결 가능하다.
• 점화식 그 자체로 이해할 수 있다.

2. 부분 문제의 중복

• 해결했던 부분 문제를 또 해결해야 하는 경우가 발생한다.
• 이미 해결한 문제를캐싱, 메모이제이션하여 해결할 수 있다.

전체 1️⃣, 3️⃣, 1️⃣, 5️⃣
a₀ → 1, a₁ → 3, a₂ → 3, a₃ → 8

a3을 결정할 때 a2, a1만 고려해도 된다.
→ aᵢ = max(aᵢ-₁, aᵢ-₂ + kᵢ)

// 정수 N을 입력 받음
n = 4;
// 모든 식량 정보 입력 받기
array = [1, 3, 1, 5];

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = new Array(100).fill(0);

// 다이나믹 프로그래밍 진행(보텀업)
d[0] = array[0];
d[1] = Math.max(array[0], array[1]);

for(let i = 2; i < n; i++) {
	d[i] = Math.max(d[i - 1], d[i - 2] + array[i]);

}
// 계산된 결과 출력
console.log(d[n - 1])