백준 15624번 [피보나치 수 7](C++)-yes6686- 티스토리

백준 문제 풀이: 15624 [피보나치 수 7]

---

문제 링크: https://www.acmicpc.net/problem/15624

문제 설명:

n번째 피보나치 수를 구하는 문제로, 결과를 1,000,000,007로 나눈 나머지를 출력합니다. 피보나치 수의 정의는 다음과 같습니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

---

문제 해결 코드

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

long long int dp[1000001];

int main() {
    int n;
    cin >> n;
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i] %= MOD;
    }
    cout << dp[n];
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 활용하여 피보나치 수를 효율적으로 계산합니다.
• 구현 세부사항:
  • dp 배열을 이용해 F(0)부터 F(n)까지의 피보나치 수를 순차적으로 계산합니다.
  • 매 단계에서 계산 결과를 MOD로 나눈 나머지를 저장하여 오버플로를 방지합니다.
• 시간 복잡도: O(n)
  • F(n)을 계산하는데 한 번의 for문만 사용됩니다.
• 공간 복잡도: O(n)
  • dp 배열에 n개의 값을 저장합니다.

---

결과

주어진 n에 대해 n번째 피보나치 수를 효율적으로 계산합니다. 결과는 항상 1,000,000,007로 나눈 나머지로 출력되며, 매우 큰 n값에서도 정확한 결과를 제공합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!