프로그래머스 코딩테스트 풀이(js) > 멀리뛰기(lv2)

문제 🔽

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

다른사람 풀이 🔽

function solution(n) {
    var answer = 0;
    var dp=[];
    dp[1]=1;
    dp[2]=2;
    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2] %1234567;
    }
    answer=dp[n];
    return answer%1234567;
}

내풀이🔽

1. 실패 ❌ => ( 시간초과 : dfs로 재귀 쓰면 너무 오래걸림 ) 

// nC0 ~ nCn 까지 하면 될듯 하다 
function solution(n) {
    var answer = 0;    
    const dfs =(count) =>{
        if(count>n){
            return 0;
        }else if(count===n){
            ++answer
            return 0;
        }
        dfs(count+1);
        dfs(count+2);
    }
    
    dfs(0)
    return answer%1234567;
}

2. 성공 ⭕ => ( 피보나치 수열이용 ) 

function solution(n) {

    if(n===1){
        return 1
    }
    if(n===2){
        return 2
    }

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

    return array[n];
}

 

 

느낀점🔽

array[i] = (array[i-2]+array[i-1]) %1234567 의 값과

array[i] = array[i-2]%1234567+array[i-1]%1234567의 값과 같다