https://www.acmicpc.net/problem/2579
dp[0] = arr[0];
dp[1] = arr[0] + arr[1];
dp[0]
에 저장되어 있으므로, 두 계단을 오르는 경우의 최대 점수는 arr[0] + arr[1]
이다.dp[2] = Math.max(arr[0], arr[1]) + arr[2];
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]); // 마지막 계단까지의 최대 점수