Algorithm
[Baekjoon]14495번 피보나치 비스무리한 수열 - Javascript
호밀이
2024. 1. 10. 22:53
https://www.acmicpc.net/problem/14495
14495번: 피보나치 비스무리한 수열
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보
www.acmicpc.net
문제
피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.
1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...
자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!
입력
자연수 n(1 ≤ n ≤ 116)이 주어진다.
출력
n번째 피보나치 비스무리한 수를 출력한다.
예제 입력 1 복사
10
예제 출력 1 복사
19
문제풀이(1)
15624번 피보나치 수 7과 같은 DP 문제이다. 조건은 조금 다르다.
f(n) = f(n-1) + f(n-3) 해당 조건에 맞게 로직을 구현하면 된다.
f(1) = f(2) = f(3) = 1
또한, Int 범위를 벗어나는 경우가 있기 때문에 Bigint를 사용해야한다.
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());
const dp = [BigInt(1), BigInt(1), BigInt(1)];
for (let i = 3; i < N; i++) {
dp.push(dp[i - 1] + dp[i - 3]);
}
console.log(dp.at(-1).toString());