10826번

10826번 - 피보나치 수 4

처음에 행렬을 이용해서 풀려고 했는데, 범위가 10000까지 밖에 되지 않았다.

그래서 그냥 DP를 이용해서 피보나치 수를 구했다.

근데 N=10000 일때 피보나치 수가 long long 을 벗어나고, unsigned long long 까지 벗어난다고 하였다..

그래서 어쩔 수 없이 string 을 써서 문제를 풀었다.

operator + 를 오버라이딩하여 string 끼리의 덧셈 연산을 재정의 했다.

<정답 코드>

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
string D[10001];
 
string operator + (string A, string B)
{
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    string ans;
    int i = 0;
    int up = 0;
    while (i < A.size() && i < B.size())
    {
        int temp = (A[i] - '0') + (B[i] - '0') + up;
        if (temp >= 10)
        {
            temp -= 10;
            up = 1;
        }
        else
        {
            up = 0;
        }
        ans += (temp + '0');
        i++;
    }
    while (i < A.size())
    {
        int temp = (A[i] - '0') + up;
        if (temp >= 10)
        {
            temp -= 10;
            up = 1;
        }
        else
        {
            up = 0;
        }
        ans += (temp + '0');
        i++;
    }
    while (i < B.size())
    {
        int temp = (B[i] - '0') + up;
        if (temp >= 10)
        {
            temp -= 10;
            up = 1;
        }
        else
        {
            up = 0;
        }
        ans += (temp + '0');
        i++;
    }
    if (up == 1)
    {
        ans += (1 + '0');
    }
    
    reverse(ans.begin(), ans.end());
    return ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    D[0] = '0';
    D[1] = '1';
    for (int i = 2; i <= n;i++)
    {
        D[i] = D[i - 2] + D[i - 1];
    }
 
    cout << D[n] << endl;
 
    return 0;
}