[백준] 2156. 포도주 시식(자바스크립트/javascript/node.js/js/다이나믹프로그래밍/동적프로그래밍/동적계획법)

 

 

문제를 풀기 위한 아이디어

dp 배열을 만든다. dp[N]에는 포도주의 개수가 N개일 때 최댓값이 저장될 것이다.

dp[1] = wine[1] (포도주가 1개밖에 없을 때에는 무조건 1개의 포도주를 마시는게 최댓값이다.)

dp[2] = wine[1] + wine[2] (포도주가 2개밖에 없을 때에는 무조건 2개의 포도주를 모두 마시는게 최댓값이다.)

dp[3] = (wine[1] + wine[2] ,  wine[2] + wine[3] , wine[1] + wine[3]) 이 3가지 경우에서 가장 큰 값이 최댓값이 된다. (연속해서 3잔을 먹을 순 없기 때문에)

 

dp[4]부터는 dp[N]을 어떻게 구할 수 있을까?

위의 그림이 모든 것을 설명해준다. 즉 저 위의 3가지 경우 중 최댓값이 dp[N]이 된다.

 

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let wine = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n")
  .map((element) => Number(element));
const number = wine[0];

const dp = new Array(number + 1);
dp[1] = wine[1];
dp[2] = wine[1] + wine[2];
dp[3] = Math.max(wine[1] + wine[2], wine[2] + wine[3], wine[1] + wine[3]);

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

console.log(dp[number]);