[JS] 피보나치 함수 - 백준 1003

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제

시간복잡도

O(n)

해결방법

dp[i] = ["0 호출 수", "1 호출 수"]로 두고 계산하며 저장한다.

 

위와 같이 dp[i]의 왼쪽은 dp[i-1], 오른쪽은 dp[i-2]를 호출하므로 0과 1이 호출된 수가 담긴 배열을 그대로 더해주면 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString().split("\n");

let max_num = Math.max(...input.slice(1));
let dp = [
  [1, 0],
  [0, 1],
  [1, 1],
];
for (let i = 3; i <= max_num; i++) {
  let tmp = [];
  tmp[0] = dp[i - 1][0] + dp[i - 2][0];
  tmp[1] = dp[i - 1][1] + dp[i - 2][1];
  dp[i] = tmp;
}
for (let i = 1; i <= input[0]; i++) {
  let tmp = dp[parseInt(input[i])];
  console.log(`${tmp[0]} ${tmp[1]}`);
}