[백준] 피보나치수 2, 피보나치수 3, 파도반 수열 (javascript)

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

2748번: 피보나치 수 2

 

 

🤔 해결방법

1. dp 배열 초기화

2. 0번째, 1번째 수 0, 1로 지정

3. i번째 = i-2번째 + i-1번째라는 규칙으로 for문 작성

이 때, BigInt 사용

4. 마지막 출력에서 toString사용 

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");

const n = Number(input[0]);

function solution(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i < n + 1; i++) {
    dp[i] = BigInt(dp[i - 2]) + BigInt(dp[i - 1]);
  }
  return dp[n].toString();
}

console.log(solution(n));

 

피보나치 수는 i번째 = i-2번째 + i-1번째 라는 규칙을 가지고 있다.
그런데 예를들어 90번째 피보나치 수는 '2,880,067,194,370,816,000'의 엄청 큰 수이다.
javascript에 존재하는 한계점으로 인해 정확한 수를 표시할 수 없기 때문에 BigInt 객체 형식으로 바꾸어 피보나치 수를 계산해야 했다.
BigInt는 Number 원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수를 표현할 수 있는 내장 객체이다.
마지막 출력 단계에서 BigInt의 값을 진수로 표현시켜주는 내장 toString 메서드 사용해줘야 한다.

 

 

 

 

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

2748번: 피보나치 수 2

 

 

🤔 해결방법

1. 피사노 주기로 dp 배열 초기화

2. 0번째, 1번째 수 BigInt(0), BigInt(1)로 지정

3. i번째 = (i-2번째 + i-1번째) % BigInt(1000000) 라는 규칙으로 for문 작성

4. 마지막 출력에서 toString사용 

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");

const n = BigInt(input[0]);

// 피사노 주기
const pisano = 1500000;
const mod = n % BigInt(pisano);

function solution(n) {
  const dp = new Array(pisano).fill(BigInt(0));
  dp[0] = BigInt(0);
  dp[1] = BigInt(1);
  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 2] + dp[i - 1]) % BigInt(1000000);
  }
  return dp[n];
}

console.log(solution(mod).toString());

 

피보나치 수열에서 특정 수로 나눈 나머지는 주기를 가지는데, 이를 피사노 주기라 한다.
피사노 주기는 모듈로 연산의 피연산자가 10^k일 때, 피사노 주기는 15*10^(k-1)이 된다.
따라서 1000000으로 나눈 나머지이기 때문에 k가 6이되므로 피사노 주기는 15*10^(6-1) = 1500000이다.

 

 

 

 

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

9461번: 파도반 수열

 

 

🤔 해결방법

1. dp 배열 초기화

2. 0번째, 1번째, 2번째 수를 0, 1, 1로 지정

3. i번째 = i-2번째 + i-3번째 라는 규칙으로 for문 작성

4. n번째 요소 출력

 

 

🔑 풀이

const input = require("fs")
  // .readFileSync("/dev/stdin")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");

const t = Number(input[0]);
let number = []; // 테스트케이스 담는 배열
for (let i = 1; i <= t; i++) {
  number.push(Number(input[i]));
}

// 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 =>  i번째 = i-2번째 + i-3번째

function solution(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = dp[2] = 1;

  for (let i = 3; i < n + 1; i++) {
    dp[i] = dp[i - 2] + dp[i - 3];
  }
  return dp[n];
}

number.forEach((e) => console.log(solution(e))); // 테스트케이스 하나씩 넣어주고 값 출력

 

규칙찾아서 점화식만 세우니 쉽게 풀 수 있었다.

dp 문제는 이 정도 수준의 문제만 나왔으면 좋겠다.. 😂