[프로그래머스 lev2/JS] 멀리 뛰기

문제 출처

프로그래머스 lev2 - 멀리 뛰기

문제

나의 풀이

1차 시도(시간초과)

function solution(n) {
  let jump = [1,2];
  let tmp = [];
  let answer=0;

  function longJump (L, sum) {
    if (sum>n) return;
    if (sum==n) {
      answer++;
    }
    else {
      for (let i=0; i<jump.length; i++) {
        tmp[L]=jump[i];
        longJump(L+1, sum+jump[i]);
        tmp.pop();
      }
    }
  }
  longJump(0,0)
  return answer % 1234567;
}

console.log(solution(4))

2차 시도(시간초과)

function solution(n) {
  let answer=0;
  function longJump (sum) {
    if (sum>n) return;
    if (sum==n) {
      answer++;
    }
    else {
      longJump(sum+1);
      longJump(sum+2);
    }
  }
  longJump(0)
  return answer % 1234567;
}

console.log(solution(4))

다른 풀이

재귀로 시간 초과 발생하면, 동적계획법으로 쪼개보기

function solution(n) {
  let dy = Array.from({length:n+2}, () => 0);
  dy[1]=1;
  dy[2]=2;
  for (let i=3; i<=n+1; i++) {
    dy[i] = (dy[i-2] + dy[i-1]) % 1234567;
  }
  return dy[n] % 1234567;
}

console.log(solution(4))