[BOJ] 10826 : 피보나치 수 4 - travelbeeee

문제 : https://www.acmicpc.net/problem/10826

---

[ 알고리즘풀이 ]

 최대 Input이 10,000입니다. 10,000번 째 피보나치는 int, long long 형으로도 모두 표현할 수 없으므로 문자배열을 이용한 덧셈으로 문제를 해결해야합니다.

 ( 문자배열을 이용한 큰 수 덧셈 포스팅 : https://travelbeeee.tistory.com/193 )

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

string string_add(string a, string b) {
	int sum = 0;
	string result;
	while (!a.empty() || !b.empty() || sum) {
		if (!a.empty()) {
			sum += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty()) {
			sum += b.back() - '0';
			b.pop_back();
		}
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}
	reverse(result.begin(), result.end());
	return result;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string first = "1", second = "1", temp;
	int N;
	cin >> N;
	if (N == 0){
		cout << 0;
		return 0;
	}
	for (int i = 0; i < N - 2; i++) {
		temp = string_add(first, second);
		first = second;
		second = temp;
	}
	cout << second;

	return 0;
}

---