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

백준 문제 풀이: 11444 [피보나치 수 6]

---

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

문제 설명:

피보나치 수열의 n번째 항을 구하는 문제입니다. 단, n은 최대 10¹⁸까지 주어질 수 있으며, 결과를 1,000,000,007로 나눈 나머지를 출력해야 합니다.

피보나치 수열의 정의는 다음과 같습니다:

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

---

문제 해결 코드

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

typedef long long ll;

map<ll, ll> memo;

// 피보나치 수 계산
ll fibonacci(ll n) {
    if (memo[n]) return memo[n];
    if (n == 0) return memo[n] = 0;
    if (n == 1) return memo[n] = 1;

    if (n % 2 == 0) {
        // F(2k) = F(k) * (F(k+1) + F(k-1))
        ll k = n / 2;
        return memo[n] = (fibonacci(k) * ((fibonacci(k + 1) + fibonacci(k - 1)) % MOD)) % MOD;
    } else {
        // F(2k+1) = F(k+1)^2 + F(k)^2
        ll k = (n + 1) / 2;
        return memo[n] = (fibonacci(k) * fibonacci(k) % MOD + fibonacci(k - 1) * fibonacci(k - 1) % MOD) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;

    cout << fibonacci(n) << '\n';
    return 0;
}

예제

입력:
10

출력:
55

입력:
100000

출력:
150075197

---

코드 설명

• 분할 정복을 활용한 피보나치 계산:
  • 피보나치 수열을 일반적인 점화식을 사용해 계산하면 O(n)의 시간 복잡도가 소요됩니다. 하지만, 분할 정복을 활용하면 O(log n)으로 계산할 수 있습니다.
  • 피보나치 수열의 특성을 이용하여 F(2k)와 F(2k+1)를 효율적으로 계산합니다.
• 메모이제이션:
  • 계산된 값을 map에 저장하여 중복 계산을 방지합니다.
• 모듈러 연산:
  • 모든 계산 과정에서 1,000,000,007로 나눈 나머지를 저장하여 값이 커지는 것을 방지합니다.

시간 복잡도

• 시간 복잡도: O(log n)
• 분할 정복을 활용하여 n을 절반으로 줄이며 계산하므로 매우 효율적입니다.

---

결과

코드는 n이 매우 큰 값일 때도 효율적으로 피보나치 수를 계산하며, 메모이제이션과 모듈러 연산을 통해 정확성과 효율성을 보장합니다.

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