백준 1003 JS 풀이

구하는 값

피보나치 구할 때 0, 1 번째 값 몇번 사용하는지

핵심 아이디어

피보나치 1,2,3,4,5 하다보면 규칙이 보임

fibo[1] = fibo[1] , fibo[2] = fibo[0] + fibo[1] 이고 그 이후는 이전 값을 사용하기 때문에

피보나치 n을 구할 때 0번째 값은 fibo[n-1]의 값과 동일하고, 1번째 값은 fibo[n]의 값과 동일함

따라서 0, 1 번째가 사용된 횟수는 fibo[n-1], fibo[n]값을 구해주면 됨

코드

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

let ts = input[0] * 1;
let line = 1;
while (ts--) {
    const n = input[line++] * 1;

    if (n === 0) {
        console.log(1, 0);
        continue;
    }

    const d = new Array(n).fill(0);

    d[0] = 0;
    d[1] = 1;

    for (let i = 2; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    console.log(d[n - 1], d[n]);
}

처음엔 재귀를 사용해서 하향식을 썼지만 시간초과뜸 그래서 반복문 형태인 상향식으로 바꿈