백준[10826] - 피보나치 수4

문제

백준 10826 문제 보기

접근 방법

일반적인 피보나치 수열의 문제를 풀듯이 dp를 활용해 문제를 풀수는 있다. 하지만 이는 약 1500번째 언저리 피보나치 수까지만 유효하다. 왜냐하면 1500 번째 근처 수열에서 long long의 범위를 넘어간다.
문제에서의 N은 10000이고 해당 수까지의 수열을 구해야 한다. 따라서 문자열을 활용해 직접 덧셈을 진행한다.

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string dp[10001];
int n;

string calc(string s, string s2) {
    string ret;
    int len, len2;
    int a, b, carry_before, carry_now;

    len = s.length();
    len2 = s2.length();

    carry_now = 0;

    if (len < len2) {

        for (int i = 0; i < len2 - len; i++) {

            s.insert(s.begin(), '0');
        }

        len = len2;
    } else if (len2 < len) {

        for (int i = 0; i < len - len2; i++) {

            s2.insert(s2.begin(), '0');
        }
    }

    for (int i = len - 1; 0 <= i; i--) {

        a = s[i] - '0';
        b = s2[i] - '0';

        carry_before = carry_now;

        if (a + b + carry_before < 10) {

            carry_now = 0;
            ret += (a + b + carry_before) + '0';
        } else {

            carry_now = 1;
            ret += (a + b + carry_before - 10) + '0';

            if (i == 0 && carry_now == 1) ret += '1';
        }
    }

    reverse(ret.begin(), ret.end());

    return ret;
}

int main() {
    cin >> n;
    dp[0] = '0';
    dp[1] = '1';
    for (int i = 2; i <= n; i++) {
        dp[i] = calc(dp[i - 1], dp[i - 2]);
    }

    cout << dp[n];
    return 0;
}