[C++] 백준 10826번 피보나치 수 4

피보나치 수 문제입니다.

먼저 다이나믹 프로그래밍 기법을 이용해
DP[i] = DP[i-1] + DP[i-2]의 점화식을 사용했습니다.

이때 값의 길이가 너무 길어져서 오버플로우가 발생하므로 string으로 저장을 했습니다. 
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 DP[10010];

	cin >> n;
	
	DP[0] = '0';
	DP[1] = '1';

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

	cout << DP[n] << endl;

	return 0;
}