[BaekJoon] 2579번 계단 오르기

▶ 문제 : http://acmicpc.net/problem/2579

2579번: 계단 오르기

 

▶ 코드 :

let input = require('fs').readFileSync(`BaekJoon/testcase.txt`).toString().split('\n');

const [N, ...temp] = input;
const stairs = temp.map(n => Number(n));
const dp = Array(N).fill(0);

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

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

console.log(dp[N-1])

 

▶ 문제 풀이:

1. 동적 프로그래밍(DP)을 사용하는 문제이다. 

2. 초기 input으로 들어온 점수를 stairs배열에 저장한다. 각 층에서의 최대값은 dp 배열에 저장한다.

3. 연속된 3칸은 오를 수 없고, 마지막 계단은 밟아야한다. 또한 첫 시작이 0번째 칸이 아닐수도 있기에 0, 1, 2 번째 계단의 초기값을 계산해서 넣어준다. => Math.max() 사용

  - 0번째 : stairs[0]의 값을 그대로 가진다.

  - 1번째 : stairs[1] 의 값과 stairs[0] + stairs[1] 값, 즉 바로 1번째 칸으로 가는 경우와 0번째 칸을 밟고 1번째 칸을 오르는 경우 중 큰 값을 저장한다.

  - 2번째 : 연속된 3칸을 오를 수 없기에, stairs[0] + stairs[2] 와 stairs[1] + stairs[2] 의 값 중 더 큰 값을 저장한다.

4. 이후 3번째 칸부터는 현재 칸의 점수와 이전 칸의 점수 그리고 이전 칸으로부터 한칸 건너뛴 i-3 번째의 dp 값을 합친 값과 현재 칸의 점수와 전전칸까지(i-2)의 dp에 저장된 값을 합친 값을 비교한다. 

  - 이렇게 되면 연속된 3칸을 오르는 경우를 배제할 수 있기때문.

5. 결과적으로 stairs는 각 칸에서의 점수를 나타내는 배열인 것이고, dp에 저장된 값은 연속된 3칸을 오르지 않으면서 계단을 올랐을때의 최대값을 저장한 배열이라고 생각할 수 있다.

6. 연산 후 결과를 출력하면 끄읕