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

문제링크

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

문제풀이

dynamic programming을 이용해서 풀수 있다. 코드에서 dp[n][0] 은 (n+1)번째 계단을 밟는데, n번째 계단을 밟고 올라온 경우의 점수합이고 dp[n][1]은 (n+1)번째 계단을 밟는데, n-1번째 계단을 밟고 올라온 경우의 점수합을 의미한다.  

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [stairCnt, ...stairs] = input.map((n) => Number(n));

let dp = Array.from({ length: stairCnt }, () => {
    return [0, 0];
});

// [연속으로 밟는경우, 연속으로 밟지 않는 경우]
dp[0] = [stairs[0], stairs[0]];
dp[1] = [dp[0][0] + stairs[1], stairs[1]];

for (let idx = 2; idx < stairCnt; ++idx) {
    dp[idx][0] = stairs[idx] + dp[idx - 1][1];
    dp[idx][1] = stairs[idx] + Math.max(dp[idx - 2][0], dp[idx - 2][1]);
}

console.log(Math.max(dp[stairCnt - 1][0], dp[stairCnt - 1][1]));

지양해야 되는 패턴

처음에 문제를 풀 때 예상과 다르게 값이 나왔는데 알고보니 `const dp = Array(10).fill([0,0])` 라는 코드 때문이었다. `const dp = Array(10).fill([0,0])` 와 같은 패턴은 모든 요소가 동일한 배열 [0,0]을 참조하게 만들고 따라서 dp 배열의 값을 변경할 때 모든 요소가 동시에 변경된다.  따라서 `const dp = Array.from({length:10}, ()=>[0,0])` 처럼 dp 배열을 개별적으로 초기화해아 한다.