[백준]JS 2579번 계단 오르기

문제

계단 오르기 문제

규칙

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

풀이

dp를 활용한 문제이다. 처음에는 마지막 계단을 반드시 밟아야 한다기에 거꾸로 밟아내려오도록 풀이를 시도하였으나, 가독성이 떨어져 (n-1, n-2, n-3 같은 것들로 채워진...) 정신이 아득해졌기 때문에 Math.max를 이용하여 dp Array 초기 세팅을 하도록 하였다.

const input = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((x) => +x);

let n = input.shift();

let dp = Array(n).fill(0);
dp[0] = input[0];
dp[1] = Math.max(input[0] + input[1], input[1]);
dp[2] = Math.max(input[0] + input[2], input[1] + input[2]);

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

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

1. 0으로 채워진 dp Array를 생성한다.
2. 0 ~ 2번 인덱스는 Math.max를 이용하여 최댓값을 할당하여 준다.
3. 3번 인덱스부터는 미리 계산한 0 ~ 2번 인덱스를 활용해 각각 한 칸과 두 칸 올라간 값 중 최댓값을 구하여 할당해준다.
4. 마지막 칸은 무조건 밟는 것이 규칙이기 때문에 마지막 칸에 할당된 값을 출력한다.