백준 / 수학 / 11444번 / 피보나치 수 6 / JS

문제 간단설명

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();

 

 

도가뉴 항등식을 이용해 풀이했다.

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

이 외에도 claude에게 물어보니, 행렬의 거듭제곱으로 풀이하는 방법도 있던데 나중에 알아봐야겠다.