[JS][멀리뛰기]

Programmers 멀리뛰기 문제

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

1칸은 1가지
2칸은 2가지
3칸은 3가지
4칸은 5가지

수상한 낌새가 나더니 이는 피보나치 수열과 같게 동작하고 있었다.

여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요.

이는 DP로 해결하라는 문제라는 것을 뜻한다고 한다...(이번에 알게 되었습니다..)
그래서 정리를 해보자면...

DP( 다이나믹 프로그래밍 )

큰 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. 이 방법은 각 하위 문제의 해결책을 저장하고, 이를 재사용하여 각 하위 문제를 한 번만 해결하게 됩니다.
따라서 이를 재귀를 진행하면서 계속해서 1234567로 나눠주면서 진행을 하면은 정답이 나올 것 같다.

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

function fibo(n){
    var dp = [];  //dp배열 생성
    [dp[1], dp[2]] = [1,2]; // 1,2가주어졌을 때 각각 1,2 의 초기값 부여
     for(let i = 3; i <= n; i++)
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567;  //피보나치  + 1234567로 나눠주는 로직 추가 
    return dp[n];
}