피보나치 함수 (1003번) [node.js, JavaScript]

피보나치 함수 (1003번) [node.js, JavaScript]

피보나치 함수 (1003번) [node.js, JavaScript]

문제 설명

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.

두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.

fibonacci(0)은 0을 출력하고, 0을 리턴한다.

fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

의사코드

N번째 f(0)과 f(1)의 호출 개수를 따로 구분하여 countObj 객체에 저장합니다. N을 인덱스로 잡고 0과 1의 개수는 일반 피보나치 수를 구하는 것과 마찬가지로 f(n) = f(n-1) + f(n-2) 식을 가지게됩니다. 입력값중 가장 큰값 N까지의 피보나치 0과 1의 호출개수를 구하고 해당하는 입력값의 요소을 출력합니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().split("

"); const cnt = +input.shift(); const list = [...input]; const countFibonacci = n => { const countObj = { zero: [1, 0], one: [0, 1] }; const { zero, one } = countObj; if (n <= 1) { return countObj } for (let i = 2; i < n+1; i++) { zero.push(zero[i-1] + zero[i-2]); one.push(one[i-1] + one[i-2]); } return countObj; }; const {zero, one} = countFibonacci(Math.max(...list)); for(let i = 0; i < cnt; i++) { num = list[i]; console.log(`${zero[num]} ${one[num]}`); }

from http://jinblog123.tistory.com/240 by ccl(A) rewrite - 2021-12-07 04:02:14