백준 11444 c++ "피보나치 수 6" -PlusUltraCode-

https://www.acmicpc.net/problem/11444

[필자 사고]

자 왜우자. 주어진 숫자가 말도 안되게 크다??
이분 탐색 분할정복 이런식으로 logN 시간복잡도로 이용해야 되는 문제다.반드시

 

해당 문제는 어느정도 수학을 알고 있어야 된다.

f(2k) = f(k){2*f(k+1)-f(k)} 와 f(2k+1) = f(k)^2 + f(2k)^2 의 형태로 구할 수 있다.

즉 fib(n/2) 로 탐색을 하면서 반환값을 f(k)와 f(k+1) 형태로 반환해주고

 

재귀 형태로 구해나가면 문제를 풀 수 있다.

[코드 해설]

문제 개요

피보나치 수열은 0과 1로 시작해,
각 항이 이전 두 항의 합으로 정의되는 수열입니다.

하지만 이 문제에서는 입력 n이 최대 10¹⁸에 이를 수 있으므로,
일반적인 반복문이나 DP로는 계산이 불가능합니다.
따라서 O(log n) 시간 복잡도의 빠른 제곱 분할(Fast Doubling) 방식을 사용해야 합니다.

---

알고리즘 핵심 아이디어

피보나치 수에는 다음과 같은 항등식이 존재합니다.

F(2k)   = F(k) × [2F(k+1) − F(k)]
F(2k+1) = F(k)² + F(k+1)²

이 식을 이용하면, F(k)와 F(k+1)만 알고 있으면
F(2k)와 F(2k+1)을 한 번의 계산으로 구할 수 있습니다.

이를 통해 n을 절반씩 줄여가며 재귀적으로 계산하면
시간 복잡도는 O(log n)으로 줄어듭니다.

---

함수별 설명

1. fib(long long n)

• 기능: n번째 피보나치 수 F(n)과 F(n+1)을 한 번에 구합니다.
• 반환형: pair<long long, long long> 형태로,
  first는 F(n), second는 F(n+1)을 의미합니다.

(1) 기저 조건

n == 0일 때는 (0, 1)을 반환합니다.
이는 F(0) = 0, F(1) = 1에 해당하는 기본 정의입니다.

(2) 분할 단계

n을 절반(n / 2)으로 나눈 뒤,
fib(n / 2)를 재귀적으로 호출합니다.
이때 반환된 (a, b)는 각각 F(k)와 F(k+1)입니다.

(3) 짝수 항 계산

F(2k)를 계산하기 위해 다음 식을 사용합니다.

F(2k) = F(k) × [2F(k+1) − F(k)]

여기서 2F(k+1) − F(k)가 음수가 될 수 있으므로
+MOD를 한 후 %MOD로 처리해 항상 양수로 만듭니다.

(4) 홀수 항 계산

F(2k+1)은 다음 식으로 구합니다.

F(2k+1) = F(k)² + F(k+1)²

모든 계산은 MOD = 1,000,000,007로 나머지 연산을 적용합니다.

(5) 결과 선택

• n이 짝수면 (F(2k), F(2k+1))을 반환합니다.
• n이 홀수면 (F(2k+1), F(2k) + F(2k+1))을 반환합니다.

이렇게 하면 한 번의 재귀 호출로 F(n)과 F(n+1)을 모두 얻을 수 있습니다.

---

2. main()

• 사용자로부터 n을 입력받습니다.
• fib(n)을 호출하여 (F(n), F(n+1))을 얻습니다.
• F(n)을 출력합니다 (% MOD 연산 포함).

---

정리

항 계산식 비고

F(2k)	F(k) × [2F(k+1) − F(k)]	짝수 번째 항 계산
F(2k+1)	F(k)² + F(k+1)²	홀수 번째 항 계산
복잡도	O(log n)	빠른 분할 정복

---

결론

이 알고리즘은 큰 수의 피보나치 항을 매우 효율적으로 계산할 수 있습니다.
n = 10¹⁸과 같은 초대형 입력도 단 몇 밀리초 내에 처리할 수 있으며,
행렬 거듭제곱보다 구현이 간단하고 메모리 사용량도 적습니다.

[소스 코드]

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

typedef pair<ll, ll> Node;

Node fib(ll n) {
	if (n == 0) {
		return { 0LL,1LL };
	}

	Node half = fib(n / 2);
	ll a = half.first;
	ll b = half.second;

	ll t = (2 * b % MOD - a + MOD) % MOD;
	ll c = (a * t) % MOD;

	ll d = (a * a % MOD + b * b % MOD) % MOD;
	
	if (n % 2 == 0) {
		return { c,d };
	}
	else {
		return { d, (c + d) % MOD };
	}
}

int main(void) {
	ll n;
	cin >> n;
	Node result = fib(n);
	cout << result.first % MOD;
}