[프로그래머스] 멀리 뛰기 (JavaScript)

프로그래머스 멀리 뛰기

문제풀이

방법의 가지수를 1부터 구해나가면 피보나치 수열을 나타내는 것을 알 수 있다. 메모이제이션을 적용하여 시간복잡도를 줄였다.

구현코드

const MOD = 1234567;
const dp = [0, 1, 2];

function solution(n) {
    return fivo(n);
}

function fivo(n){
    if(n <= 2) return dp[n];
    if(dp[n]) return dp[n];
    else return dp[n] = (fivo(n - 1) + fivo(n - 2)) % MOD;
}