프로그래머스 [Lv. 2] 멀리 뛰기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(n) {
    let dp = Array(n+1).fill().map(() => 1);
    dp[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = (dp[i-2] + dp[i-1]) % 1234567;
    };
    const answer = dp[n];
    return answer;
}

정답 코드 2

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

풀이 방법

• 규칙은 다음과 같다.

1	2	3	4	5	6	7	8	9	10
1	2	3	5	8	13	21	34	55	89

느낀점

• 1과 2로 dfs를 돌리려다가 규칙을 찾아서 dp를 만들었다.
• 저장하면서 계산하는 방식이 더 빠른것 같다.