[백준/BOJ] 15624번 피보나치 수 7 (C++)

개요

이 글은 백준 15624번 피보나치 수 7 문제를 풀이한다.

요약

$n$을 입력받아 $n$번째 피보나치 수를 $1,000,000,007$로 나눈 나머지를 출력하라.

입력 조건

$0 \leq n \leq 1,000,000$

분석

피보나치 수열은 다음과 같이 정의된다.

\[F_{n} = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 2 \end{cases}\]

주어진 $n$의 범위가 작기 때문에, 일반적인 피보나치 수열을 구하는 방법으로도 충분히 해결할 수 있다.

풀이

주어진 $n$에 대해, DP를 이용하여 피보나치 수열을 구현하면 된다.

예시 답안

#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;

int solve(void) {
  int n; cin >> n;

  vector<int> f(n + 2); // n = 0이어도 f[1]을 사용하기 위해 n + 2로 설정
  f[0] = 0; f[1] = 1;
  for (int i = 2; i <= n; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % MOD;
  }
  cout << f[n];

  return 0;
}

원본 소스 코드는 Hiyabye/Baekjoon - 15624.cpp 에서 확인할 수 있다.

문제 해결 팁

재귀를 이용한 피보나치 수열 구현은 시간복잡도가 $\mathcal{O}(2^N)$으로 매우 느리다. 따라서 이 방법은 사용하지 않는 것이 좋다.

반복문을 이용한 DP를 사용하여 피보나치 수열을 구현하면 시간복잡도가 $\mathcal{O}(N)$으로 훨씬 빠르다.

마무리

도움이 되었다면 반응이나 댓글을 남겨주시면 감사하겠습니다.

추가적인 의견이나 피드백 또한 언제든지 환영입니다! :)