[프로그래머스/JS] 멀리 뛰기 (Lv2) / DP

문제요약

나의 코드 및 설명

• 백트래킹으로 문제를 해결하려고 했는데 시간초과로 인해 실패했다.

var jump = [1,2];
var cnt = 0;
function dfs(depth, temp, n){
    if (temp >= n) {
        if (temp == n){
            cnt += 1;
        }
        return
    }
    
    for (var j of jump){
        dfs(depth+1, temp+j, n);
    }
}

function solution(n) {
    var answer = 0;
    dfs(0, 0, n);
    answer = cnt % 1234567
    return answer;
}

다른 코드 및 설명

• DP를 활용하여 문제를 해결할 수 있다.
• 1칸을 뛰어야 할 때 : 1가지
• 2칸을 뛰어야 할 때 : 2가지
• DP[3] = DP[1] + DP[2] -> DP[n] = DP[n-1] + DP[n-2]

function solution(n) {
    var answer = 0;
    var arr = Array(n+1).fill(0);
    
    console.log(arr); // [0,0,0,0,0]
    
    arr[1] = 1;
    arr[2] = 2;
    for (let i = 3; i <= n; i++){
        arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
    }
    
    console.log(arr); // [0,1,2,3,5]
    
    answer = arr[n]; 
    return answer;
}

피드백

자바스크립트 기본 문법에 어느정도 적응이 되고 있지만, 자바스크립트 기본 문법을 익히는 동안 그동안 공부했었던 알고리즘을 다소 까먹은 것 같다.. 다시 열심히 해서 알고리즘 실력을 끌어 올려야겠다.