[백준] 피보나치 함수

문제 요약

아래와 같이 N번째 피보나치 수를 구하는 C++ 함수가 존재합니다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

위의 함수를 호출해서 피보나치 수를 구할때 출력되는 0과 1의 횟수를 구하려고 합니다.

예시

• fibonacci(2) 호출시 0 ⇒ 1번, 1 ⇒ 1번 호출됨
• fibonacci(3) 호출시 0 ⇒ 1번, 1 ⇒ 2번 호출됨

 

나의 생각

먼저 문제에서 제공한 fibonacci 함수를 그대로 구현 후 활용하면 속도에서 문제가 발생할 것이라 생각하였습니다. 이전에 피보나치수를 구한 결과를 다시 계산하지 않기 위해서 이전 계산의 결과를 배열에 기억하고 있다가 활용하는 방식을 사용하였습니다.

const fs = require('fs');
const [N, ...input] = fs
    .readFileSync('example.txt')
    .toString()
    .trim()
    .split('\n')
    .map(Number);

let numberList = [];
let consoleList = [];

function fibonacci(n, temp) {
    if (numberList[n]) {
        temp[0] += consoleList[n][0];
        temp[1] += consoleList[n][1]
        return numberList[n];
    }

    if (n === 0) {
        temp[0] = 1;
        return 0;
    } else if (n === 1) {
        temp[1] = 1;
        return 1;
    } else {
        return fibonacci(n - 1, temp) + fibonacci(n - 2, temp);
    }
}

for (let i = 0; i <= Math.max(...input); i += 1) {
    consoleList[i] = [0, 0];
    numberList[i] = fibonacci(i, consoleList[i]);
}

let output = [];

for (let i = 0; i < N; i += 1) {
    output.push(consoleList[input[i]].join(' '));
}

console.log(output.join('\n'));