Level2️⃣ - 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

해석

n의 값에 따라 결과값이 어떻게 나오는지 정리하면 다음과 같다.

n = 1 ➡ 1

n = 2 ➡ 2

n = 3 ➡ 3

n = 4 ➡ 5

즉, 피보나치 수열이다. 그렇다면 피보나치 수열을 구현하면 되는데 구현 방법에는 재귀와 dp가 있다.

재귀로 호출할 경우에는 수가 커짐에 따라 스택 프레임 용량을 초과할 수 있기 때문에 dp로 구현해야한다.

그리고 n이 최대 2000이라면 숫자로 표현할 수 있는 범위를 초과할 수 있기에 모듈러 연산을 활용해야한다.

 

코드

const fibo = (n) => {
    const dp = Array.from({length:n+1}).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2; i<=n; i++) dp[i] = (dp[i-1] % 1234567 + dp[i-2] % 1234567) % 1234567;
    return dp[n];
    
}

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