[C++] 백준 10870번 피보나치 수 5

피보나치 수 문제입니다.

수의 범위가 너무 크기 때문에
int, long long으로 선언하더라도 오버플로우가 나게 됩니다.

string으로 값을 받아서 계산해주었습니다.

 

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

string sum(string x, string y)
{
	int num;
	int carry = 0;
	string result;

	reverse(x.begin(), x.end());
	reverse(y.begin(), y.end());

	while (x.length() < y.length()) {
		x += '0';
	}
	while (x.length() > y.length()) {
		y += '0';
	}

	for (int i = 0; i < x.length(); ++i) {
		num = (x[i] - '0' + y[i] - '0' + carry) % 10;
		result += to_string(num);
		carry = (x[i] - '0' + y[i] - '0' + carry) / 10;
	}
	if (carry != 0) {
		result += to_string(carry);
	}

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

	return result;
}

int main(int argc, char* argv[])
{
	int n;
	string a;
	string b;
	string result;

	cin >> n;

	a = '0';
	b = '1';

	if (n == 0) {
		result = "0";
	}
	if (n == 1) {
		result = "1";
	}

	for (int i = 2; i <= n; ++i) {
		result = sum(a, b);
		a = b;
		b = result;
	}

	cout << result << endl;

	return 0;
}