[피보나치] 프로그래머스 '멀리뛰기' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=javascript 

프로그래머스

2. 설명

이 문제는 피보나치 형태의 규칙을 따른다.

1칸 움직이는 방법 => 1
2칸 움직이는 방법 =>2
3칸 움직이는 방법 =>3
4칸 움직이는 방법 =>5
5칸 움직이는 방법 =>8

fib(n) = fib(n-1) + fib(n-2) 의 형태와 동일하다!

하지만 이 문제에서 0칸은 고려하지 않으니, 가독성을 위해 배열에 처음부터 [0,1,2]를 할당해주고 시작한다. 아니면 기존의 피보나치처럼 [0,1,1]을 할당해준 후 n+1의 값을 리턴해줘도 된다.

오버플로우를 방지하기 위해 값을 1234567로 나눈 나머지 자체를 집어넣어준다. 마지막으로 dp의 n번째 인덱스를 1234567로 나눈 나머지를 리턴해주면 정수 오버플로우 문제 없이 통과된다!

3. 코드

정답 코드)

function solution(n) {
    let dp=[0,1,2];

    for(let i=3;i<=n;i++){
        dp[i] = (dp[i-1]+dp[i-2])% 1234567;
    }

    return dp[n]%1234567;
}

// 또는

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

처음에 작성한 코드)

function solution(n) {
     if(n<=2) return n;
    
     return (solution(n-1) + solution(n-2)) % 1234567;
}