[boj] 2579. 계단 오르기 (node.js)

문제 요약

BOJ 2579 계단 오르기

• 입력: 계단의 총 개수와 각 계단을 밟으면 얻을 수 있는 점수가 주어진다.
• 출력: 얻을 수 있는 최대 점수는?
• 한 번에 한 계단씩 또는 두 계단씩만 오를 수 있다.
• 시작 게단을 제외하고 3개 연속으로 밟을 수 없다.

풀이

• N번째 계단을 올랐을 때 얻을 수 있는 총 점수를 계산하기 위해
  1. 두 계단 올라서 N번째 계단에 도착하는 경우
  2. 한 계단 올라서 N번째 계단에 도착하는 경우
• 이 두 가지로 전체 경우를 분류하여 동적 프로그래밍 알고리즘을 구성한다.
• 점화식은 세 계단을 연속으로 밟을 수 없으므로 2번 경우는 직전 경우가 두 계단 올라야만 한다. 따라서 한 계단 오르는 경우, 두 계단 오르는 경우의 최댓값을 모두 배열에 저장해 활용한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = input();
  let score = [];
  const arr = new Array(N);
  for (let i = 0; i < N; i++) {
    score.push(Number(input()));
  }
  arr[0] = [score[0], 0];
  arr[1] = [score[0] + score[1], score[1]];
  for (let i = 2; i < N; i++) {
    arr[i] = new Array(2);
    arr[i][0] = arr[i - 1][1] + score[i];
    arr[i][1] = Math.max(arr[i - 2][0], arr[i - 2][1]) + score[i];
  }
  console.log(Math.max(arr[N - 1][0], arr[N - 1][1]));
  process.exit();
});