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

문제: https://www.acmicpc.net/problem/2156
알고리즘 분류: 다이나믹 프로그래밍, DP

문제 파악

• 포도주 잔을 선택하면 그 잔의 포도주는 모두 마셔야 함
• 연속으로 3잔을 모두 마실 수 없음
• 가능한 많은 양의 포도주를 마시는 것이 목표

접근 방법: 동적 프로그래밍

• 계산이 진행되면서 바뀌는 상황에서, 최적의 전략
• 계산했던 걸 저장해서 재사용

각 위치에서 최대로 마실 수 있는 포도주의 양 구하기

경우의 수
1. 현재 포도주를 마시고, 이전 포도주도 마신 경우 (2연속)
2. 현재 포도주를 마시고, 이전 포도주는 마시지 않은 경우
3. 현재 포도주를 마시지 않는 경우

DP 상태
dp[i][j]: i번째 포도주까지 고려했을 때, j개의 연속된 포도주를 마셨을 때의 최대 양

• dp[i][0]: i번째 잔을 마시지 않았을 때의 최대값
• dp[i][1]: i번째 잔을 마시고, i-1번째 잔은 마시지 않았을 때의 최대값
• dp[i][2]: i번째 잔을 마시고, i-1번째 잔도 마셨을 때의 최대값

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);

const n = input[0];  // 포도주 잔의 개수
const wines = [0];  // 포도주의 양 (인덱스를 1부터 시작하기 위해 0 추가)

// 포도주 양 입력 처리
for (let i = 1; i <= n; i++) {
    wines.push(input[i]);
}

// 동적 프로그래밍 배열 초기화
// dp[i][j]: i번째 잔까지 고려했을 때, j개 연속으로 마셨을 때의 최대 양
// dp[i][0]: i번째 포도주를 마시지 않은 경우
// dp[i][1]: i번째 포도주를 마시고, i-1번째는 마시지 않은 경우
// dp[i][2]: i번째 포도주를 마시고, i-1번째도 마신 경우
const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));

// 초기값 설정
dp[1][0] = 0;             // 첫 번째 포도주를 마시지 않음
dp[1][1] = wines[1];      // 첫 번째 포도주를 마심

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

// 최대값 계산
const maxAmount = Math.max(dp[n][0], dp[n][1], dp[n][2]);
console.log(maxAmount);

각 상태 점화식

dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) → 현재 잔을 마시지 않으면 이전 상태 중 최대값 선택
dp[i][1] = dp[i-1][0] + wines[i] → 현재 잔을 마시고, 이전 잔은 마시지 않은 경우
dp[i][2] = dp[i-1][1] + wines[i] → 현재 잔과 이전 잔을 연속으로 마시는 경우

참고
deun블로그
https://bedecked-operation-4d1.notion.site/99-12-TIL-DP-2156-1d6eb405261e8085b424f799344a670d