[JavaScript] 백준 2579 : 계단 오르기

class : 3

level : silver 3

문제 링크 : 계단 오르기

2579번: 계단 오르기

 

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n').map(Number);
const N = input.shift();
let answer = 0;
input.unshift(0);/// 시작점 포함하기
let a = new Array(N+1).fill(0);
let b = new Array(N+1).fill(0);
a[1] = input[1];
b[1] = input[1];
for(let i = 2; i < N + 1; i++){
    a[i] = Math.max(a[i-2]+input[i],b[i-2]+input[i]);
    b[i] = a[i-1]+input[i];
}
console.log(Math.max(a[N],b[N]));

 

풀이방법

접근 방법으로는 Greedy를 생각했으나 반례가 생각보다 많아 DP(Dynamic Programming)로 선회하였다.

시작을 0번 index로 잡고 시작을 하였다.

N번째 계단을 밟기 위해서는 두 가지 경우가 있다.

1. N-2번째 계단에서 바로 N번째 계단으로 오는 방법

2. N-3번째 계단에서 바로 N-1번째 계단으로 온 후 N번째 계단으로 오는 방법

 

1번 방법은 a라는 Array에 담고 2번 방법은 b라는 Array에 담았다.

첫번째 계단만 동일하게 a와 b 모두 값을 넣어 주었다.

 

마지막에는 a와 b중 더 큰 것을 출력하였다.

 

느낀점
Dynamic Programming에서 점화식 세우는 것이 관건이다.

매우 빠르게 할 수 있다고 생각이 든다.