백준 2156 JS 풀이

구하는 값

포도주 가장 많이 마시는 방법

근데 연속해서 3개는 마실 수 없다는 조건이 있음

핵심 아이디어

점화식을 구해보면

n번째 포도주에 도달할 수 있는 경우의 수는 3가지로 그 중 가장 큰 값이 DPtable[n]이 된다.

1. n번째를 안마시는 경우 → n-1번째 도달한 경우중 가장 큰 값 d[n-1]
2. n번째를 마시는데 n-1번째를 마시는 경우 → n과 n-1을 마시는 경우이므로 n-3번째에 도달 한 경우 중 가장 큰값 d[n-3]에 n, n-1번째 값을 더한 값
3. n번째를 마시는데 n-2번째를 마시는 경우 → n과 n-2을 마시는 경우이므로 n-3번째에 도달 한 경우 중 가장 큰값 d[n-2]에 n번째 값을 더한 값

즉 d[i] = Math.max(d[i - 1], d[i - 2] + graph[i], d[i - 3] + graph[i] + graph[i - 1]) 가 됨

초기값을 3개 구해주고 DP ㄱㄱ

코드

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

const n = input[0] * 1;
const d = new Array(n).fill(0);

const graph = [];
for (let i = 1; i <= n; i++) graph.push(input[i] * 1);
// console.log("graph", graph);

d[0] = graph[0];
d[1] = graph[0] + graph[1];
d[2] = Math.max(graph[0] + graph[1], graph[0] + graph[2], graph[1] + graph[2]);

// console.log(d);
for (let i = 3; i < n; i++) {
    // 점화식 -> n 칸 도달하는 경우 3가지 중 가장 큰값
    d[i] = Math.max(d[i - 1], d[i - 2] + graph[i], d[i - 3] + graph[i] + graph[i - 1]);
}

console.log(d[n - 1]);