[프로그래머스 lev2/JS] 피보나치 수

문제 출처

프로그래머스 lev2 - 피보나치 수

나의 풀이

시간 초과 발생하는 거 보니 메모이제이션 필요한 것 같다.

function solution(n) {
  function F (number) {
    if (number === 0) return 0;
    if (number === 1) return 1;
    else return F(number-1) + F(number-2);
  }
  return (F(n) % 1234567);
}

마지막에만 나눠주는 게 아니라 매번 나눠줘야 했음. 이렇게 풀었는데도 마지막 문제 2개가 런타임 에러가 뜬다.
⇒ 왜 에러가 뜨냐면, 13,14 TC에서는 js 엔진이 가능한 재귀호출의 깊이(10000)를 초과했기 때문임. 즉, 재귀를 통해 풀면 안 된다는 소리…

function solution(n) {
  let tmp=Array.from({length:n}, () => 0);
  function F(N) {
    if (tmp[N]>0) return tmp[N];
    if (N===1) return 1;
    if (N===0) return 0;
    else return tmp[N]=(F(N-1)%1234567)+(F(N-2)%1234567);
  }
  return F(n)%1234567;
}

// console.log(solution(12));
// console.log(solution(3)); // 2
console.log(solution(5)); // 5

다른 풀이

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

// console.log(solution(12));
// console.log(solution(3)); // 2
console.log(solution(5)); // 5