피보나치 수 4

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기

문제 풀이 step 1

  • dp[n] = n 번째 피보나치 수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 점화식은 “dp[n] = dp[n - 1] + dp[n - 2]” 입니다.
  • 점화식을 이용해서 base 부터 n 번쨰 피보나치 수까지 배열을 채운 후 n 번째 피보나치 수를 출력하면 정답입니다.
  • 특이점은 n 의 범위가 너무 넓어서 Number 형으로 표현할 수 있는 범위를 넘어가기 때문에 BigInt 형을 사용해야 합니다.
  • 그리고 출력할 때도 Number 형으로 변환하면 Infinity 값이 되므로, String 형으로 변환해서 출력해야 합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

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

const solution = (input) => {
	const n = Number(input[0]);

	// base
	const dp = [0n, 1n];
	for (let i = 2; i <= n; i++) {
		// 점화식
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return String(dp[n]);
};

console.log(solution(input));