4. 계단 오르기

const { stat } = require("fs");

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";

let [N, ...stairs] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

const dp = new Array(N + 1).fill(0);

stairs = [0, ...stairs];
dp[1] = stairs[1];
dp[2] = stairs[1] + stairs[2];

for (let i = 3; i <= N; i++) {
  const before_1 = dp[i - 3] + stairs[i - 1] + stairs[i];
  const before_2 = dp[i - 2] + stairs[i];

  dp[i] = Math.max(before_1, before_2);
}

console.log(dp[N]);