10826 피보나치 수 4

피보나치 그대로 값 계산했다가 틀린 문제ㅠ

 

10000 넣으니 음수가 나온 걸로 보아 오버플로우가 난 것 같다.

 

i64를 해도 문제니 덧셈을 문자열로 처리할 수 밖에 없었다. 

 

문자열 덧셈은 많이 짜봐서 빠르게 짰음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

using namespace std;

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

    reverse(all(a));
    reverse(all(b));


    for (int i = 0; i < min(a.size(), b.size()); i++)
    {
        int ta = a[i] - '0';
        int tb = b[i] - '0';

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

    if (a.size() < b.size())
    {
        for (int i = min(a.size(), b.size()); i < b.size(); i++)
        {
            int tb = b[i] - '0';

            res += (tb + carry) % 10 + '0';
            carry = (tb + carry) / 10;
        }
    }
    else
    {
        for (int i = min(a.size(), b.size()); i < a.size(); i++)
        {
            int ta = a[i] - '0';

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

    if (carry != 0)
        res += carry + '0';

    reverse(all(res));

    return res;
}

int     main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;

    vector<string> v(n + 1);
    v[0] = "0";
    v[1] = "1";

    for (int i = 2; i <= n; i++)
    {
        v[i] = string_sum(v[i - 1], v[i - 2]);
    }

    cout << v[n];

    return 0;
}

 

엇... 그런데 런타임 에러가 떴다???

 

혹시나 싶어서 작은 수 넣는데 0에서 문제가 생겼다

 

알고보니 v(n + 1)로 배열을 만들었더니 n이 0일 때 v[1]에 접근해서 문제였다.

 

그래서 v + 5로 만들었음

 

해결!