백준] 10826 - 피보나치 수 4

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

소스코드

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
	int n, len1, len2, carry, prevCarry;
	string fib1 = "0", fib2 = "1";

	cin >> n;
	if (n == 0)
		cout << fib1;
	else if (n == 1)
		cout << fib2;
	else
	{
		for (int i = 2; i <= n; i++)
		{
			string nextFib = "";
			prevCarry = carry = 0;
			len1 = fib1.length();
			len2 = fib2.length();
			if (len1 < len2)
			{
				for (int i = 0; i < len2 - len1; i++)
					fib1.insert(fib1.begin(), '0');
				len1 = len2;
			}
			else if (len1 > len2)
			{
				for (int i = 0; i < len1 - len2; i++)
					fib2.insert(fib2.begin(), '0');
			}

			for (int i = len1 - 1; i >= 0; i--)
			{
				int f1 = fib1[i] - '0';
				int f2 = fib2[i] - '0';

				prevCarry = carry;

				if (f1 + f2 + prevCarry >= 10)
				{
					carry = 1;
					nextFib += (f1 + f2 + prevCarry - 10) + '0';
					if (i == 0 && carry)
						nextFib += '1';
				}
				else
				{
					carry = 0;
					nextFib += (f1 + f2 + prevCarry) + '0';
				}
			}
			reverse(nextFib.begin(), nextFib.end());
			fib1 = fib2;
			fib2 = nextFib;
		}
		cout << fib2;
	}
}

Tip

이 문제는 C++에서 long long을 사용해도 오버플로우가 발생하는 문제다. 결국 큰 수의 계산을 해야되기 때문에 배열로 입력받아 처리하는 방법을 생각해야 한다.