[C++] 피보나치 수 시리즈

솔브닥 class 4+ 풀고 있었는데 거기에 피보나치 수 6 문제가 있길래 이참에 피보나치 수 문제를 쭉 풀어볼까 한다.

 

---

피보나치 수 (백준 2747번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    
    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    cout << fib[n] << '\n';
}

바텀업 dp로 풀었다. (AC)

 

---

피보나치 수 2 (백준 2748번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    
    vector<long long> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    cout << fib[n] << '\n';
}

나머지는 동일한데 n 크기만 조금 더 커졌다. 1번 문제에서 제출한 코드에 90을 입력하면 오버플로우가 나기 때문에 fib 배열의 타입을 long long으로 바꿔주었다. (AC)

 

---

피보나치 수 3 (백준 2749번)

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

 

#include <iostream>
using namespace std;

const int M = 1000000;
const int PI = 15 * (M / 10);
int fib[PI];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n;
    cin >> n;
    
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < PI; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % M;
    }

    cout << fib[n % PI] << '\n';
}

2번 문제보다 n 크기가 훨씬 커졌다. 어떻게 풀어야 하는지 감이 안 와서 질문 게시판을 슬쩍 보니 피사노 주기라는 것이 있었다. 

피사노 주기(Pisano Period)는 피보나치 수열을 어떤 정수 m으로 나눈 나머지들의 반복되는 패턴의 길이를 의미한다. 모든 m에 대해 이 주기는 존재하며, 피보나치 수열을 m으로 나누었을 때의 나머지는 일정한 패턴으로 반복된다.
일반적으로 m에 대한 주기는 규칙이 나올 때까지 구해보며 직접 찾아야 하지만, m = 10^k (k>2) 형태의 경우에는 주기가 항상 15*10^(k-1)로 고정된다. 

이 문제도 이 형태에 포함되기 때문에 주기를 고정적으로 구할 수 있다. 

주의할 점은 어차피 1,000,000의 나머지이기 때문에 fib 배열의 타입은 int로 해도 되지만, 마지막에서만 M으로 나눠주면 오버플로우가 날 수 있기 때문에 fib[i]를 계산할 때마다 나눠주어야 한다. 또 당연한 거지만 입력받을 때 n을 long long으로 입력받아야 한다! (AC)

 

---

피보나치 수 4 (백준 10826번)

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

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string addBigNum(string a, string b) {
    int carry = 0;
    string res = "";

    while (!a.empty() || !b.empty() || carry) {
        if (!a.empty()) {
            carry += a.back() - '0';
            a.pop_back();
        }
        if (!b.empty()) {
            carry += b.back() - '0';
            b.pop_back();
        }

        res += ((carry % 10) + '0');
        carry /= 10;
    }

    reverse(res.begin(), res.end());
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    
    vector<string> fib(n + 1);
    fib[0] = "0";
    if (n != 0) fib[1] = "1";
    for (int i = 2; i < n + 1; i++) {
        fib[i] = addBigNum(fib[i - 1], fib[i - 2]);
    }

    cout << fib[n] << '\n';
}

2번 문제보다 n이 커졌지만 나머지를 구하는 문제는 아니다. 2번 문제에서 제출한 코드에 90부터 입력을 넣어보면 93부터 오버플로우가 나는 것을 확인할 수 있다. long long으로도 오버플로우가 날만큼 큰 수이기 때문에 문자열로 덧셈 연산을 구현해주어야 한다. 

참고로 reverse는 문자열의 앞뒤를 뒤집는 함수이고 <algorithm> 헤더 파일에 있다. (AC)

[참고] https://changicho.tistory.com/entry/%ED%81%B0-%EC%88%98-%EC%97%B0%EC%82%B0-Big-Integer

 

string addBigNum(string a, string b) {
    int carry = 0;
    string res = "";

    while (!a.empty() || !b.empty() || carry) {
        if (!a.empty()) {
            carry += a.back() - '0';
            a.pop_back();
        }
        if (!b.empty()) {
            carry += b.back() - '0';
            b.pop_back();
        }

        res = char((carry % 10) + '0') + res;
        carry /= 10;
    }

    return res;
}

처음에는 이렇게 새로운 수를 res 맨 앞에 붙이면 마지막에 뒤집는 과정 없어도 되니까 더 편하지 않을까 싶었다. 하지만 이렇게 하면 새로운 수를 res 맨 앞에 붙일 때마다 복사가 일어나므로 훨씬 느리다.

 

실제로 10배 정도 차이가 나는 것을 볼 수 있다.

 

---

피보나치 수 5 (백준 10870번)

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

 

#include <iostream>
using namespace std;

int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    cout << fib(n) << '\n';
}

오히려 1번 문제보다 n이 작다. 재귀로도 통과될 것 같아서 재귀로 짜봤다. 당연히 dp로도 통과된다. (AC)

 

---

피보나치 수 6 (백준 11444번)

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

 

#include <iostream>
#include <vector>
using namespace std;

const int M = 1000000007;
vector<int> fib;

int findPisanoPeriod(int m) {
    fib.push_back(0);
    fib.push_back(1);
    int idx = 2;
    while (1) {
        fib.push_back((fib[idx - 1] + fib[idx - 2]) % m);
        if (fib[idx] == 1 && fib[idx - 1] == 0) {
            break;
        }
        idx++;
    }
    return idx - 1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n;
    cin >> n;

    int pi = findPisanoPeriod(M);
    cout << fib[n % pi] << '\n';
}

3번 문제와 비슷하지만 이번에는 나누는 수가 10의 거듭제곱 형태가 아니라 주기를 바로 계산할 수 없다. 그래서 이렇게 직접 주기를 구하도록 코드를 작성해보았다. 그런데 M이 너무 커서 그런지 마치 무한루프를 도는 것 같았다. 

 

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int mod = 1000000007;
map<long long, long long> m;

long long fib(long long n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else if (n == 2) return 1;
    else {
        if (m.find(n) != m.end()) {
            return m[n];
        } else {
            if (n % 2 == 0) {
                long long tmp = (fib(n / 2) * (fib(n / 2 + 1) + fib(n / 2 - 1))) % mod;
                m[n] = tmp;
                return tmp;
            } else {
                long long tmp = (fib((n + 1) / 2) * fib((n + 1) / 2) + fib((n - 1) / 2) * fib((n - 1) / 2)) % mod;
                m[n] = tmp;
                return tmp;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n;
    cin >> n;
    cout << fib(n) << '\n';
}

그래서 찾아보니 M이 너무 크기 때문에 점화식을 변형해서 2로 분할되는 점화식을 유도할 수 있는 것을 알게 되었다.

f(n) = f(n-1) + f(n-2) = f(2)f(n-1) + f(1)f(n-2)
      = 2f(n-2) + f(n-3) = f(3)f(n-2) + f(2)f(n-3)
       = 3f(n-3) + 2f(n-4) = f(4)f(n-3) + f(3)f(n-4)
       = 5f(n-4) + 3f(n-5) = f(5)f(n-4) + f(4)f(n-5)
       = ...
       = f(k+1)f(n-k) + f(k)f(n-k-1)

n이 짝수일 때, 즉 n=2k일 때, f(2k) = f(k){f(k+1)+f(k-1)}
n이 홀수일 때, 즉 n=2k+1일 때, f(2k+1) = {f(k+1)}^2 + {f(k)}^2

[참고] https://howudong.tistory.com/300

추가로, 탑다운으로 하려면 메모이제이션을 해야 한다. 이 때 M이 너무 크기 때문에 map을 사용하였다. (AC)

 

---

피보나치 수 7 (백준 15624번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int mod = 1000000007;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    
    vector<long long> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
    }

    cout << fib[n] << '\n';
}

2번 문제의 코드를 그대로 사용하되 1,000,000,007로 나눠주는 부분만 추가해줬다. (AC)