99클럽 코테 스터디 12일차 TIL - 포도주 시식 (dp)

문제: https://www.acmicpc.net/problem/2156

접근 방식

• 현재까지의 최적의 값을 dp 배열에 저장
  • 초기값으로 dp[0], dp[1], dp[2] 저장
  • 이후 다음 세 가지 경우 중 가장 큰 값 저장
    • i번째 잔을 안 마시는 경우
    • i번째만 마시는 경우
    • i-1, i번째 연속으로 마시는 경우

구현

const fs = require("fs")
const [n, ...arr] = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number)

const dp = []
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = Math.max(arr[0] + arr[2], arr[1] + arr[2], dp[1])

for (let i = 3; i < n; i++) {
  dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i])
}

console.log(dp[n - 1])

DP (Dynamic Programming) 동적 계획법

• 큰 문제를 풀기 위해, 작은 문제의 정답을 저장해두고 재사용하는 방법
• 중복되는 작은 문제(subproblem)가 있어 같은 계산을 반복하게 되거나 최적 부분 구조(optimal substructure)가 있을 때 dp 사용