[Javascript] (프로그래머스 level 2) 멀리 뛰기

[Javascript] (프로그래머스 level 2) 멀리 뛰기

💡 구글에 Javascript 풀이가 많이 없거나, 배운 점이 있으면 포스팅합니다.

내 풀이

function solution(n) {
    let count = 0;
    const arr = [];
    function DFS(L, sum) {
        if (sum > n ) return;

        if (sum >= n || L === n) {
            if (sum === n) {
                count++;
            }
        } else {
            DFS(L + 1, sum + 1)
            DFS(L + 1, sum + 2)
        }
    }
    DFS(0, 0)

    return count % 1234567;
}

이번에도 어설프게 재귀함수 배웠다고 사용해봤다가 시간초과로 실패했습니다!!

어떻게 푸는건지 궁금해서 검색해보니 이건 DP로 푸는게 맞다네요.

약간의 팁인데 결과값을 1234567로 나눈 나머지로 내라고 하는 것 자체가 “이문제는 DP입니다.”라는 힌트가 된다고 하네요.

해설 참고한 풀이

function solution(n) {
    const dp = Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;

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

    return dp[n] 
}

DP 기본예제인 피보나치 수열 문제였다.

점화식 상 dp[n] = dp[n-1] + dp[n-2] 이므로 해당 식을 사용하여 풀면된다.

배운 점, 느낀 점

기본예제라 풀이는 굉장히 쉬웠지만, 해당 풀이에 접근하기까지 재귀로 푸는 삽질을 해버린터라 많이 아쉬웠다. 어쨌든 좋은 경험했다~!