[백준] 1788

피보나치 수의 확장

문제

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

const fibo = () => {
  let i = Number(require("fs").readFileSync("/dev/stdin").toString().trim());
  if (i === 0) console.log("0\n0");
  else {
    let n = i < 0 ? -i : i;
    let dp = Array.from({ length: n + 1 }, (_) => 0);
    dp[1] = 1;
    if (i < 0)
      for (let j = 2; j <= n; j++) dp[j] = (dp[j - 2] - dp[j - 1]) % 1000000000;
    else
      for (let j = 2; j <= n; j++) dp[j] = (dp[j - 2] + dp[j - 1]) % 1000000000;
    console.log(`${dp[n] < 0 ? -1 : dp[n] === 0 ? 0 : 1}\n${Math.abs(dp[n])}`);
  }
};

fibo();

반성회

• i가 0일 때 예외처리 해주기
• n에는 i의 절대값을 넣고, 이를 길이로 갖는 dp 배열 만들기
• i가 음수일 경우, j는 실제 피보나치 인덱스의 절대값을 가진다
• i가 양수일 경우, 보편적인 피보나치 수 구하는 방법으로 계산
• 매번 계산 시마다 1,000,000,000으로 나눈 나머지를 dp 배열에 담아 오버플로우 방지
• 마지막 출력 시에는 dp[n]의 값에 따라 첫 번째 줄에 -1, 0, 1 출력 후 dp[n]의 절대값 출력