계단오르기(동적 프로그래밍)

문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드)

 

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

 

▣ 입력설명
첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

 

▣ 출력설명
첫 번째 줄에 올라가는 방법의 수를 출력합니다.

 

▣  입력예제 1

7

 

▣  출력예제 1

21

 

Tip

 

문제풀이

//강의 듣고 내가 다시 작성한 답
function solution(num){
    let answer;
    let dyTable = Array.from({length : num+1}, ()=>0);
    dyTable[1] = 1;
    dyTable[2] = 2;

    for(let k = 3; k <= num ; k++){
        dyTable[k] = dyTable[k-2] + dyTable[k-1]; 
    }

    answer = dyTable[num];
    return answer;
}

console.log(solution(7));