Level3. 프로그래머스 멀리 뛰기 - JavaScript

 

문제 설명

효진이는 1칸, 또는 2칸을 뛸 수 있다. 

칸 n이 주어졌을 때 효진이가 n에 도달할 수 있는 모든 경우의 수를 찾아야 한다. 

n이 4일 때

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(2, 1, 1)

(2, 2)

모든 경우의 수는 5번이다.

 

이 문제는 조합으로 풀 수도 있고 DP로도 풀 수가 있다.

 

DP로 푼다면 작은 문제로 나누고 이 문제들의 정답이 큰 문제를 해결할 수 있다는 규칙성을 찾아야 한다.

규칙은 F(n)에서 n이 3이상일 때 F(n) = F(n-1) + F(n-2)이다.

 

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