입력으로 주어지는 n이 말이 안되게 높은 이유로 기존 방식으로는 무조건 해결 할 수 없을 것이라는 것을 알았다.
하지만 이문제를 해결할 수 있는 수식을 생각해 냈지 못했고 일단 오답으로라도 제출 할 수 있게 문제를 해결하고 풀이를 찾아보았다. 모든 풀이에서는 메모리와 시간 문제를 이를 바로 해결하지 않고 분할 방식이나 행렬연산으로 해결하였는데 풀이를 보더라도 이해하지 못하였다. 수리능력이 부족한 까닦이기에 날 잡고 이에 대해 확실히 공부해야 겠다는 생각이 들었다.

오답

#include <iostream>
#include <stack>
#include <string>

using namespace std;

long long n;
long long ary[100000000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    ary[0] = 0;
    ary[1] = 1;
    ary[2] = 1;
    ary[3] = 2;
    if (n < 4) {
        ary[n];
    }
    else {
        for (int i = 2; i <= n; i++) {
            ary[i] = ary[i - 2] + ary[i - 1];
        }
        cout << ary[n]%1000000007;
    }


    return 0;
}

정답 출처

#include <iostream>
#include <map>
// BOJ - 11444 Fibonacci Number 6
#define DIV		1000000007LL
using namespace std;

map<long long, long long> f;

long long fibo(long long n) {	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 1;
	if (f.count(n) > 0) return f[n];

	if (n % 2 == 0) {
		long long m = n / 2;
		long long temp1 = fibo(m - 1); long long temp2 = fibo(m);
		f[n] = ((2LL * temp1 + temp2) * temp2) % DIV;
		return f[n];
	}
	long long m = (n + 1) / 2;
	long long temp1 = fibo(m); long long temp2 = fibo(m - 1);
	f[n] = (temp1 * temp1 + temp2 * temp2) % DIV;
	return f[n];
}

int main(void) {
	long long n;

	cin >> n;
	cout << fibo(n);

	return 0;
}