PS/백준
백준 / 수학 / 11444번 / 피보나치 수 6 / JS
KimMinJun
2025. 1. 13. 20:19
문제 간단설명
n이 주어졌을 때, n번째 피보나치 수를 출력하면 된다.
제한 사항
- n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
성공 코드
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
.readFileSync(filePath)
.toString()
.trim()
.split('\n')
.map((el) => el.trim());
const n = BigInt(input.shift());
const DIVISOR = BigInt(1e9 + 7);
const memo = [];
function solution() {
memo[0] = 0n;
memo[1] = 1n;
memo[2] = 1n;
const result = fibonacci(n);
console.log(result.toString());
}
function fibonacci(n) {
if (memo[n]) {
return memo[n];
}
const half = n / 2n;
if (n % 2n === 0n) {
memo[n] =
(fibonacci(half) * (2n * fibonacci(half - 1n) + fibonacci(half))) %
DIVISOR;
} else {
memo[n] =
(fibonacci(half) * fibonacci(half) +
fibonacci(half + 1n) * fibonacci(half + 1n)) %
DIVISOR;
}
return memo[n];
}
solution();
도가뉴 항등식을 이용해 풀이했다.
피보나치 수 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
ko.wikipedia.org
이 외에도 claude에게 물어보니, 행렬의 거듭제곱으로 풀이하는 방법도 있던데 나중에 알아봐야겠다.