Level2. 프로그래머스 피보나치 수 - JavaScript

 

DP를 이용하여 풀 수 있습니다.

DP는 큰 문제를 나누어 작은 문제를 해결하면서 점차 점차 큰 문제를 해결하는 방식입니다. 

핵심은 memoization인데 작은 문제의 정답을 기록해 두어서 다음 문제를 풀 때 활용합니다.

 

문제 설명

피보나치의 경우 f(n) = f(n-1) + f(n-2)입니다.

기본적으로 f(0) = 0 f(1) =1 입니다. f(2) = f(1) + f(0) 이므로 f(2)는 1입니다.

다음으로 f(3) = f(2) + f(1) 이므로 f(3)은 2입니다.

이런 식으로 0 1 1 2 3 5 8 ... 으로 커집니다.

 

function solution(n) {
    const divider = 1234567
    const dp =  [0, 1];
    for( let i = 2; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % divider
    }
    return dp[n];
}