[백준] 2579 계단 오르기 Node.js

문제

https://www.acmicpc.net/problem/2579

문제풀이

• dp 배열 초기값 설정:
  1. dp[0] = arr[0];
     • 첫 번째 계단까지 도달했을 때의 최대 점수는 첫 번째 계단의 값과 같다.
  2. dp[1] = arr[0] + arr[1];
     • 두 번째 계단까지 도달했을 때의 최대 점수는 첫 번째 계단을 오르고 두 번째 계단을 오른 경우의 합이다. 첫 번째 계단을 오르는 경우의 최대 점수는 dp[0]에 저장되어 있으므로, 두 계단을 오르는 경우의 최대 점수는 arr[0] + arr[1]이다.
  3. dp[2] = Math.max(arr[0], arr[1]) + arr[2];
     • 세 번째 계단까지 도달했을 때의 최대 점수는 두 가지 경우 중 큰 값을 선택한다.
       • 1번째 계단 → 3번째 계단 오르는 경우
       • 2번째 계단 → 3번째 계단 오르는 경우
     • 따라서, 첫 번째 계단과 두 번째 계단 중 더 큰 값을 세 번째 계단과 더하여 dp[2]에 저장한다.
• 반복문을 통해 나머지 계단에 대한 최대 점수를 구한다.
  • 현재 계단을 밟았을 때와 이전 계단을 밟고 현재 계단을 밟지 않았을 때 중 더 큰 값을 선택하여 현재 계단까지의 최대 점수를 구한다. 이를 반복하면 마지막 계단까지의 최대 점수가 나온다.

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [n, ...arr] = require('fs').readFileSync(filePath).toString().trim().split(/\s/).map(Number);
const dp = [];

dp[0] = arr[0]; // 첫 번째 계단까지의 최대 점수
dp[1] = arr[0] + arr[1]; // 두 번째 계단까지의 최대 점수
dp[2] = Math.max(arr[0], arr[1]) + arr[2]; // 세 번째 계단까지의 최대 점수

for (let i = 3; i < n; i++) {
  // 현재 계단을 밟았을 때와 이전 계단을 밟고 현재 계단을 밟지 않았을 때 중 큰 값을 선택
  dp[i] = Math.max(arr[i] + arr[i - 1] + dp[i - 3], arr[i] + dp[i - 2]);
}

console.log(dp[n - 1]); // 마지막 계단까지의 최대 점수