백준 24416 알고리즘 수업 - 피보나치 수 1

링크

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

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

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

  return [dp[n], cnt].join(" ");
};

console.log(solution(input));

재귀를 하지 않고 동적계획법으로 푼 피보나치 수열이다.

동적계획법이 부족해 따로 카테고리를 만들고 여러 문제를 풀어보려고 한다.