[백준1003_자바스크립트(javascript)] - 피보나치 함수

🔴 문제

피보나치 함수

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const db = new Array(41).fill(0);

db[0] = [1, 0];
db[1] = [0, 1];

function fibo(n) {
  if (db[n] !== 0) {
    return db[n];
  } else {
    const [left0, left1] = fibo(n - 1);
    const [right0, right1] = fibo(n - 2);
    db[n] = [left0 + right0, left1 + right1];
    return db[n];
  }
}

for (const n of inputs.map((it) => Number(it))) {
  fibo(n);
  console.log(...db[n]);
}

🟢 풀이

피보나치 함수의 경우 N번째를 N-1, N-2로 쪼갤수 있어 DP 문제유형이다.
여러개의 테스트 케이스가 주어지기 때문에 피보나치 함수를 만들어 주었다.
N은 40보다 작은 수이기 때문에 크기가 40인 배열을 0으로 초기화 해주었다. fibo 함수 내부에서는 일반적인 재귀형태로 구현해주었는데 db 배열에 값이 있다면 함수를 종료하게 해서 일반 재귀보다 훨씬 빠른 DP를 적용시켰다.

🔵 Ref