[백준] 2579. 계단 오르기 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍)

 

문제를 풀기 위한 아이디어 

우선 dp배열을 만든다. 이 배열의 dp[n]에는 계단이 n개일 때 얻을 수 있는 점수의 최댓값이 저장될 것이다.

그리고 입력값으로 주어진 각 계단마다의 점수들을 stairs라는 배열에 저장한다. 이 때 계단 또한 1번째 계단이면 stairs[1]로 생각할 수 있게끔 stairs[0]에도 값을 넣어주면 편하다. (배열의 인덱스로 헷갈리지 않기 위함)

dp[1] = stairs[1]     : 계단이 1개일 때에는 계단 1개를 무조건 밟는 것이 최대 점수이다. (그리고 어차피 도착계단을 무조건 밟아야 하기 때문)

dp[2] = dp[1] + stairs[2]     : 계단이 2개일 때에는 계단 2개 다 무조건 밟는 것이 최대 점수이다. (계단을 연속해서 2개 밟는 것 까지는 괜찮다.)

dp[3] = (stairs[1], stairs[2])중 최댓값 + stairs[3]    : 계단이 3개일 때에는 일단 stairs[3]은 도착 지점이니까 무조건 밟아야 하고, stairs[1]과 stairs[2] 중 최댓값이라는 것은 계단을 연속해서 3개를 밟을 수는 없기 때문에 1번째 계단과 2번째 계단 중 더 값이 큰 것을 밟고 + 3번째 계단을 밟는 다고 생각하면 된다.

 

그렇다면 dp[4]부터는 어떻게 구할 수 있을까?

dp[n] = (dp[n-3] + stairs[n-1] + stairs[n]   ,   dp[n-2] + stairs[n] ) 중 최댓값을 골라서 저장하면 된다.

왜 이런 점화식이 구해졌냐면, 우선 n번째 계단 직전에 밟은 계단은 n-1번째 계단을 밟았을 수도 있고 n-2번째 계단을 밟았을 수도 있다. 

1. n번째 계단 직전에 n-1번째 계단을 밟았을 경우 : dp[n-3] + stairs[n-1] + stairs[n]

n번째 직전에 n-1번째 계단을 밟으면, n-1번째 직전에는 n-3번째 계단을 밟았을 수 밖에 없다. 왜냐하면 n-1번째 직전에 n-2번째 계단을 밟아버리면 n-2, n-1, n번째 계단을 모두 밟는 것이 되므로 문제에서 주어진 연속한 세 계단을 밟을 수 없다는 규칙에 위배되기 때문이다.

그러므로 d[n] = dp[n-3] + stairs[n-1] + stairs[n]이 된다.

 

2. n번째 계단 직전에 n-2번째 계단을 밟았을 경우 : d[n-2] + stairs[n]

이 경우에는 그냥 d[n] = d[n-2] + stairs[n]이 된다. 왜냐하면 n-2 번째 전의 상황은 신경쓸 필요가 없기 때문이다. 빨간색으로 표시한 것처럼 n-4 , n-2, n 으로 밟았을 수도 있고 n-3, n-2, n 순으로 밟아도 주어진 규칙에 위배되는 것이 없기 때문에 모두 허용된다. 그러므로 n-2번째까지 밟았던 점수의 최댓값에 n번째 계단 점수를 더하면 되는 것이다.

 

 

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let stairs = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n")
  .map((element) => Number(element));
const N = stairs[0];
const dp = Array.from(new Array(N + 1));
dp[1] = stairs[1];
dp[2] = dp[1] + stairs[2];
dp[3] = Math.max(stairs[1], stairs[2]) + stairs[3];
for (let i = 4; i <= N; i++) {
  dp[i] = Math.max(
    dp[i - 3] + stairs[i - 1] + stairs[i],
    dp[i - 2] + stairs[i]
  );
}
console.log(dp[N]);