[백준 2579번 / js / dp] 계단 오르기

문제

 

각각 계단에는 일정한 점수가 쓰여있고 계단을 밟으면 그 계단에 쓰여있는 점수를 얻을 수 있다. 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 갈때 얻을 수 있는 최댓값을 구해라.

 

조건

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

 

입력

입력의 첫째 줄은 개수, 둘째 줄부터 제일 아래에 놓인 계단부터 순서대로 쓰여있는 점수이다. 

계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

 

 

dynamic programming

 

작은 문제들의 정답을 메모하여 그보다 큰 문제를 풀어나갈때 메모한 작은 문제의 결과값을 이용하는 알고리즘이다.
그래서 큰 문제가 주어지더라도 작은 문제로 쪼개서 그 안에서 규칙을 찾아보는게 좋은 것 같다

 

풀이

조건에 따른 규칙을 생각해보니 n개의 계단까지 갈 때 n-2계단과 n-3 계단 중 하나는 반드시 밟아야한다. 한번에 한 계단이나 두 계단을
오를 수 있으므로 n-2계단과 n-1계단을 지나야한다고 생각할 수 있지만 n-1 계단을 지닐 경우 n-2,n-1, n계단을 순서대로 다 밟은 경우를 뻬주어야한다. 그러므로 3개의 계단을 연속해서 밟으면 안되는 걸 생각했을 때 
  1. n-2계단까지 도착하여 한계단을 건너뛰어서 n계단에 도착
  2. n-3계단에 도착하여 한계단 건너뛰고 n-1계단, n계단을 밟아 도착
하는 두가지 경우가 있다는 걸 알 수 있다. 규칙을 찾은대로 코드를 짜보면 다음과 같다

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((a) => Number(a));

let n = input[0];
let arr = Array.from({ length: n + 1 }, (a) => 0);
arr[0] = 0;
arr[1] = input[1];
arr[2] = input[1] + input[2];
for (let i = 3; i <= n; i++) {
  arr[i] = Math.max(
    arr[i - 2] + input[i],
    arr[i - 3] + input[i] + input[i - 1]
  );
}

console.log(arr[n]);

 

파싱이 끝나면 각 계단까지 가는 최댓값을 저장해줄 배열 arr를 만들어주고, 시작점, 1번째 계단, 2번째 계단까지 가는 최댓값을 저장해준다
3부터 구해야하는 n개의 계단까지 반복문을 돌며 규칙에서 찾은대로 n-2까지 갈 때의 최댓값에 n번째 계단에서 얻는 점수를 더한값과 n-3까지의 최댓값에 n-1번째 계단에서 얻는 점수, n번째 계단에서 얻는 점수를 더한값중 큰 값을 배열에 저장해주면 구하는 값은 arr[n]에 저장된다!