프로그래머스 - [Level 3] 멀리뛰기(JAVASCRIPT)

프로그래머스 멀리뛰기

카테고리 : DP

전형적인 DP(Dynamic Programming) 문제이다.
단순하게 경우의 수를 카운팅하여 점화식을 만들었다.

n=1 일 때
[1]
n=2 일 때
[1,1]
[2]
n=3 일 때
[1,1,1]
[1,2]
[2,1]

이에 따라서 
dp[n]=dp[n-1]+dp[n-2]라는 점화식이 도출된다.

한가지 주의할점은 리턴 값에 % 1234567을 적용하면
n이 특정 기준 값을 넘어갈 경우 null이 나온다.
점화식 계산 시 % 처리를 해줘야한다.

* 자바스크립트
실제 정수 계산 가능범위 (2 ^ 53 - 1) ~ -(2 ^ 53 - 1)

Number의 MAX_SAFE_INTEGER 와 MIN_SAFE_INTEGER 값의 범위이다.

Number.MAX_SAFE_INTEGER ~ Number.MIN_SAFE_INTEGER
= 9007199254740991 ~ -9007199254740991
= (253 - 1) ~ -(253 - 1)

소스 코드

function solution(n) {
    let arr=Array.from(Array(n).fill(0));
    arr[1]=1;
    arr[2]=2;
    for(let i=3;i<=n;i++){
        arr[i]=(arr[i-1]+arr[i-2])%1234567;
    }
    return arr[n];
}

Refrence

• http://ouoiouoi.blogspot.com/2017/05/javascript-number.html