[JS] 연습문제 > 멀리 뛰기

/* 
 * 1 칸을 뛰는 방법 = 1 가지
 * 2 칸을 뛰는 방법 = 2 가지
 * (n+2 칸을 뛰는 방법) = (n+1 칸을 뛰는 방법) + (n 칸을 뛰는 방법)
 * f_1 = 1, f_2 = 2 인 피보나치 수열
 * 
 */
 
 function solution(n) {

    var arr = [0,1,2];
    
    for(var i = 3; i <= n; i++){
        
        arr[i] = (arr[i-2] + arr[i-1])%1234567;   
    }
    return arr[n];
}

이번 문제의 핵심은 피보나치 수열이다.

1칸을 뛰는 방법은 (1칸)으로 1가지가 있고, 2칸을 뛰는 방법은 (1칸,1칸),(2칸)으로 2가지가 있다.

3칸을 뛰는 방법은 (1칸,1칸,1칸),(1칸,2칸),(2칸,1칸)으로 3가지..4칸을 뛰는 방법은 5가지다.

N+2칸을 뛰는 방법 = N+1 칸 방법 + N+2칸 방법이므로 피보나치 수열을 이용해 문제를 풀 수 있다.

 

효진이가 뛸 수 있는 방법이 1칸, 2칸인데 편의를 위해 0을 0인덱스 자리에 추가해준다.

arr의 3번 인덱스부터 값을 추가해주면 되니 i는 3부터 시작한다.