[Algorithm] 범위에 따른 피보나치 수 구하는 방법
피보나치 수는 일반적으로 재귀적으로 구할 수 있지만 이 경우 함수 호출이 많아져서 많은 시간이 소요되게 됩니다. n 의 값에 따라서 이에 대해서 어떻게 접근해야할지가 다릅니다. 여러 문제를 해결하며 이를 알아보도록 하겠습니다.
BAEKJOON 247
n 번째 피보나치 수를 구하는 문제입니다. n 의 범위가 45 보다 작거나 같기 때문에 int 자료형으로 해결이 가능합니다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int fibo[46];
fibo[0] = 0;
fibo[1] = 1;
for (int i=2;i<46;i++){
fibo[i] = fibo[i-1] + fibo[i-2];
}
int N;
cin >> N;
cout << fibo[N] << "\n";
return 0;
}
int 형은 아래와 같이 46 번째 까지 표현이 가능합니다.
0번째: 0
1번째: 1
2번째: 1
3번째: 2
4번째: 3
5번째: 5
6번째: 8
7번째: 13
8번째: 21
9번째: 34
10번째: 55
11번째: 89
12번째: 144
13번째: 233
14번째: 377
15번째: 610
16번째: 987
17번째: 1597
18번째: 2584
19번째: 4181
20번째: 6765
21번째: 10946
22번째: 17711
23번째: 28657
24번째: 46368
25번째: 75025
26번째: 121393
27번째: 196418
28번째: 317811
29번째: 514229
30번째: 832040
31번째: 1346269
32번째: 2178309
33번째: 3524578
34번째: 5702887
35번째: 9227465
36번째: 14930352
37번째: 24157817
38번째: 39088169
39번째: 63245986
40번째: 102334155
41번째: 165580141
42번째: 267914296
43번째: 433494437
44번째: 701408733
45번째: 1134903170
46번째: 1836311903
47번째: -1323752223
BAEKJOON 2748
2748번: 피보나치 수 2
문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를
www.acmicpc.net
마찬가지로 n 번째 피보나치를 구하는 문제입니다. n 의 범위가 커졌기 때문에 int 대신 long long 자료형으로 해결이 가능합니다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
long long fibo[90];
fibo[0] = 0;
fibo[1] = 1;
for (int i=2;i<91;i++){
fibo[i] = fibo[i-1] + fibo[i-2];
}
int N;
cin >> N;
cout << fibo[N] << "\n";
return 0;
}
BAEKJOON 2749
2749번: 피보나치 수 3
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
n 의 범위가 1,000,000,000,000,000,000 로 급격하게 뛰었습니다. 하지만 1,000,000으로 나눈 나머지를 출력하기 때문에 해결할 수 있습니다. 이를 해결하기 위해서는 피사노 주기 를 알아야 합니다. 피사노 주기란 피보나치 수를 K 로 나눈 나머지는 주기를 갖는다는 것으로 예를 통해 살펴보겠습니다.
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
fibo 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
fibo%3 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2
K = 3 일 때, 0~7 번째 수와 8~14번째 수가 주기를 이루는 걸 확인할 수 있습니다. 즉 3 으로 나누었을 때, N 번째 피보나치 수를 구하기 위해서는 주기의 길이만큼만 계산을 해주면 됩니다. 위 경우에는 8번의 계산으로 해결할 수 있으므로 O(1) 입니다.
이 때 K 의 값이 10^k' 일 때 주기는 15*10^(k'-1) 임이 성립합니다. 따라서 주어진 문제에서 1,000,000(=10^6) 이므로 주기는 1,500,000(=15X10^5) 가 되고 N 의 범위인 10^18 까지 구하지 않고 1,500,000 까지만 구한 후 주기를 이용하여 답을 구해줄 수 있습니다.
#include <iostream>
using namespace std;
long long fibo[1500000];
int main(int argc, const char * argv[]) {
fibo[0] = 0;
fibo[1] = 1;
for (int i=2;i<1500000;i++){
fibo[i] = (fibo[i-1] + fibo[i-2]) % 1000000;
}
long long N;
cin >> N;
N = N % 1500000;
cout << fibo[N] << "\n";
return 0;
}
BAEKJOON 11444
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
위에서 본 피보나치 수 3 과 마찬가지로 주기를 찾고 싶지만 1,000,000,007 로 나누기 때문에 주기를 찾는 공식이 있지 않고 직접 찾기에도 어렵습니다. 따라서 이 경우에는 아래와 같은 공식을 이용해 분할정복을 통해 구할 수 있습니다.
재귀적으로 구성하게 되면 함수 호출이 너무 많아지므로 map 을 이용해서 memorization 도 추가하였습니다.
#include <iostream>
#include <map>
using namespace std;
map<long long, long long> dic;
const long long DIV =1000000007LL;
long long fibo(long long n){
if (n<0) cout << "n<0\n";
if (n==0) return 0;
else if (n==1) return 1;
else if (dic[n] > 0) return dic[n];
else if (n%2==0) {
long long m = n/2;
long long temp1 = fibo(m-1);
long long temp2 = fibo(m);
dic[n] = (2LL*temp1+temp2)*temp2;
dic[n] %= DIV;
return dic[n];
}
else {
long long m = (n+1)/2;
long long temp1 = fibo(m);
long long temp2 = fibo(m-1);
dic[n] = temp1*temp1 + temp2*temp2;
dic[n] %= DIV;
return dic[n];
}
}
int main(int argc, const char * argv[]) {
long long N;
cin >> N;
cout << fibo(N) << "\n";
return 0;
}