백준 BOJ 2749 피보나치 수 3

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

2749번: 피보나치 수 3

2749, 11444

2749 문제 해설

재귀나 반복 문제를 풀다 보면 한 번쯤 만나는 피보나치의 수에 관한 문제다.

그런데 입력 값 n의 범위가 1~10^18사이의 정수다. 너무 크다.

그래서 1,000,000으로 나눈 나머지를 출력하라고 한다.

정해는 피사노 주기를 이용하는 것 같다.

본인은 일단 구해야 하는 피보나치의 수는 모두 구했다.

 

일단, 피보나치의 수를 살펴보자

Fn = Fn-1 + Fn-2 (n ≥ 2) 이렇게 생겼다.

단순 재귀를 이용한 풀이는 원하는 수를 구하기 위해 이전의 수 두 개를 구해야 하기 때문에 시간 복잡도 O(2ⁿ),다이내믹 프로그래밍(DP)을 이용한 풀이는 구해놓은 수를 저장해놓고 재사용하기 때문에 O(n)이다.그런데 입력값이 1,000,000,000,000,000,000 이하의 자연수이므로 DP는 불가능해 보인다.

 

이번엔 피보나치의 수 계산식을 파헤쳐보자

전개 1)

Fn = Fn-1 + Fn-2

    = 2Fn-2 + Fn-3

    = 3Fn-3 + 2Fn-4

    = 5Fn-4 + 3Fn-5 .... !! 어디서 본 수들이 나오지 않는가..? 더 나아가 보자

    = 8Fn-5 + 5Fn-6 ... 그렇다 계수들이 피보나치의 수를 이룬다.

...

    = Fk*Fn-(k-1) + Fk-1*Fn-k ... 일반화시킬 수 있다. 만약 k자리에 n/2를 넣으면..?

    = Fn/₂*Fn/₂+1 + Fn/₂-1*Fn/₂

    = Fn/₂(Fn/₂+1 + Fn/₂-1)    n을 n/₂로 줄였다 큰 성과다... log₂(n) 가능성이 보인다. 조금만 더..

    = Fn/₂(Fn/₂ + 2*Fn/₂-1)    log₂(n)이고, Fn/₂, Fn/₂-1 두 개만 구하면 된다.

만약 Fn이 짝수든 홀수든 Fn/₂, Fn/₂-1 중 한 개는 홀수, 한 개는 짝수다.

홀수 n은 단순히 n/₂를 인자로 호출할 수 없다.

홀수 처리를 위해 전개 1)처럼 k자리에 (n+1)/2를 넣어보자.

짜잔

Fn = F(n+1)/₂*F(n+1)/₂ + F(n-1)/₂*F(n-1)/₂

이로써 n이 홀수인 경우도 처리할 수 있게 됐다.

 

끝... 이야?

아니다.. 이대로 보내면 시간 초과가 나온다 (알고싶지않았다)

그래도 계산량이 많으니 더 줄일 필요가 있다. 시간복잡도는 대략 O(2^(log₂(N)) = O(N)으로 보인다.

DP를 쓰자, 입력이 너무 큰데..? 어디 저장할까....?

구한 값만 저장하면 되므로 배열은 너무 비효율적이다.

본인은 map을 썼다. O(log₂(N))

이제 끝이다.

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <map>
map<long long, long long>cache;
long long Q = 1'000'000;
long long fibo(long long X){
	if(X == 0) return 0;
	if(X == 1) return 1;
	if(cache.find(X) != cache.end()) return cache[X];
	if(X % 2 == 0){//even
		long long x_2 = fibo(X/2);
		long long x_2_1 = fibo(X/2 - 1);
		long long tmp = 2*x_2_1; tmp %= Q;
		tmp += x_2; tmp %= Q;
		long long ret = (x_2 * tmp)%Q;
		cache[X] = ret;
		return ret;
	}else{//odd
		long long x_p = fibo((X+1)/2);
		long long x_m = fibo((X-1)/2);
		x_p *= x_p; x_p %= Q;
		x_m *= x_m; x_p %= Q;
		long long ret = (x_p + x_m)%Q;
		cache[X] = ret;
		return ret;
	}
}
int main() {
	fio;
    long long N; cin >> N;
	cout << fibo(N);
	return 0;
}

 

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

11444번: 피보나치 수 6

문제 해설

2749와 거의 같은 문제다.

위의 풀이에서 나머지를 구하는 부분만 고치면 된다.

2749는 피사노주기를 이용할 수 있는 방법이 하나 더 있는 것만 다르다.