[백준 2156] 포도주 시식 with Node.js

문제 링크

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

2156번: 포도주 시식

풀이

const solve = (n, wine) => {
  if (n === 1) return wine[0];
  else if (n === 2) return wine[0] + wine[1];
  const dp = new Array(n).fill(0);
  dp[1] = wine[0];
  dp[2] = wine[0] + wine[1];
  for (let i=3; i<=n; i++) {
    dp[i] = Math.max(dp[i-3] + wine[i-2] + wine[i-1], dp[i-2] + wine[i-1], dp[i-1]);
  }
  return dp[n];
};

const [n, ...wine] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);
console.log(solve(n, wine));

1~n번째 까지의 포도주 잔이 주어졌을 때, 마실 수 있는 포도주 양의 최댓값을 dp[n]라고 하자.

 

dp[n]은 다음 세 가지 경우 중 최댓값이라고 할 수 있다.

1. dp[n-3] + (n-1)번째 포도주, n번째 포도주

2. dp[n-2] + n번째 포도주

3. dp[n-1]

 

3잔을 연속으로 마실 수 없기 때문에,

1번 경우는 dp[n-3] 이후에 n-2번째 잔을 거르고, n-1번째 잔과 n번째 잔을 연속으로 마시는 경우다.

2번 경우는 dp[n-2] 이후에 n-1번째 잔을 거르고, n번째 잔 하나를 마시는 경우다.

3번 경우는 dp[n-1]이 1번과 2번 경우보다 이미 크기 때문에 n번째 잔을 아예 마시지 않는 경우다.

 

따라서, dp[n] = MAX(dp[n-3] + arr[n-1] + arr[n], dp[n-2] + arr[n], dp[n-1]) 이라는 점화식을 세울 수 있다.

 

위 코드에서 arr에 해당하는 wine 배열이 0부터 시작하여 dp배열과 인덱스 차이가 있어,

wine배열의 인덱스는 1씩 더 빼주었다.