[Baekjoon]9507번 Generations of Tribbles - Javascript

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

9507번: Generations of Tribbles

문제

꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 koong(n)이라고 할 때,

n < 2 :                         1
n = 2 :                         2
n = 3 :                         4
n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)

이다.

여러분도 꿍 피보나치를 구해보아라.

입력

입력의 첫 번째 줄을 테스트 케이스의 개수 t (0 < t < 69)가 주어진다. 다음 t줄에는 몇 번째 피보나치를 구해야하는지를 나타내는 n(0 ≤ n ≤ 67)이 주어진다.

출력

각 테스트 케이스에 대해, 각 줄에 꿍 피보나치값을 출력하라.

예제 입력 1 복사

8
0
1
2
3
4
5
30
67

예제 출력 1 복사

1
1
2
4
8
15
201061985
7057305768232953720

 

문제풀이(1)

변형된 피보나치수를 구하면되는 문제이다.
koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)
기본적으로 주어지는 수는 1, 1, 2, 4이다.

주어지는 수의 범위가 int를 넘어가기 때문에 Bigint를 사용한다.

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

const N = input.shift();
const answer = [];

for (let i = 0; i < N; i++) {
  const dp = [1, 1, 2, 4];

  for (let j = 4; j < input[i] + 1; j++) {
    const num = BigInt(dp[j - 1]) + BigInt(dp[j - 2]) + BigInt(dp[j - 3]) + BigInt(dp[j - 4]);
    dp.push(num.toString());
  }
  answer.push(dp[input[i]]);
}

console.log(answer.join("\n"));