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

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

1003번: 피보나치 함수

 

 

📋풀이방법

1. 피보나치 수열의 특징을 이용한다

 - F(3) = F(2) + F(1) -> (F(1)+F(0)) + F(1)

 - 여기서 우리는 1과 0 이 몇번 호출 되는지 알아야한다.

 - 원래는 F(0)과 F(1)의 값을 배열에 미리 저장한다 -> arr[0] = 0, arr[1] = 1

 - 이때 우리는 0과 1이 몇 번 호출되는지 알아야 하므로 arr[0]=[0,1] , arr[1]= [1,0]으로한다.

 - 이 의미는 아래와 같다.

2. 즉 F(3)은 2가 아니고 [1, 2] 라는 값을 호출하게 된다.

3.이를 위해서는 피보나치수열을 순차적으로 저장할 때 아래와 같이 수행해야한다.

for (let j = 2; j <= n; j++) {
    fibonacci[j] = [
        fibonacci[j-1][0] + fibonacci[j-2][0], 
        fibonacci[j-1][1] + fibonacci[j-2][1]
    ];
}

-F(3)은 

[ F(2)의 0이 호출된 횟수와 F(1)의 0이 호출된 횟수,

F(2)의 1이 호출된 횟수와 F(1)의 1이 호출된 횟수 ]를 

출력한다. -> F(2)는 [1,1]을 저장하게 된다.

 

 

🤟내 제출

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");

const N = input.shift();

for (let i = 0; i < N; i++) {
    const num = input[i];

    const fibonacci = [[1, 0], [0, 1]];
    
    for (let j = 2; j <= num; j++) {
        fibonacci[j] = [
            fibonacci[j-1][0] + fibonacci[j-2][0], 
            fibonacci[j-1][1] + fibonacci[j-2][1]
        ];
    }

    console.log(fibonacci[N].join(" "));
}