2579 계단 오르기

문제 분석

알고리즘: DP

주어진 조건에 따라 두가지 경우의 수를 생각했다.

1. n-1 번째 계단과 n-3 번째 계단을 밟고, n 번째 계단을 밟은 경우

   즉, n-1번째 까지의 점수 합 + n-1 번재 계단 점수 + n번째 계단 점수

2. n -2 번째 계단을 밟고, n 번째 계단을 밟은 경우

   즉, n-2번째 까지의 점수 합 + n번째 계단 점수

보기 쉽게 표로 나타내면 다음과 같다. (밟은 경우 O, 밟지 않은 경우 X)

	n -3 번째 계단	n -2 번째 계단	n -1 번째 계단	n 번째 계단
①	O	X	O	O
②	…	O	X	O

이를 점화식으로 나타내면 다음과 같다.

주어진 수열을 A라고 하고, 계단 점수의 합을 메모제이션할 배열을 DP라고 가정한다.

DP[N] = Math.max(DP[n-2] + A[n], DP[n-3] + A[n-1] + A[n];

두 경우를 비교하여 더 큰 경우를 메모제이션한다.

풀이

위 점화식을 적용한 풀이

const [n, ...a] = require('fs')
  .readFileSync('dev/stdin')
  .toString()
  .split('\n')
  .map(Number);
const dp = new Array(n).fill(0);

dp[0] = a[0];
dp[1] = a[0] + a[1];
dp[2] = Math.max(a[0] + a[2], a[1] + a[2]);

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

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