[백준] 10826_피보나치 수 4

[문제]: 10826번: 피보나치 수 4 (acmicpc.net)

 

BigInteger 클래스를 만들어서도 풀어보자. operator+()함수의 string 파라미터는 참조형 변수가 아니다. 

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

// 이 함수는 46번 라인에서 호출됨
string operator+(string str1, string str2)
{
	string ret;
	int n = 0, carry = 0;
    // 일의 자리부터 계산하기 위해
	reverse(begin(str1), end(str1));
	reverse(begin(str2), end(str2));

	// 자릿수가 더 적은 숫자 앞에 0을 채워준다.
    // 예) 254 + 31 -> 254 + 031 
    // 물론 reverse() 함수로 인해 순서는 뒤바뀌어 있다.
	while (str1.size() < str2.size())
		str1 += '0';
	while (str2.size() < str1.size())
		str2 += '0';
	
    // 각 자리수를 더하고 올림처리
    // 그리고 각 자릿수를 더한 결과를 결과 변수 ret에 이어 붙인다.
	for (size_t i = 0; i < str1.size(); ++i) {
		n = ((str1[i] - '0') + (str2[i] - '0') + carry) % 10;
		ret += to_string(n);
		carry = ((str1[i] - '0') + (str2[i] - '0') + carry) / 10;
	}
	
    // 위 for문을 다 돌고 올림이 남으면 맨 앞자리에 넣어주면 됨
	if (carry != 0)
		ret += to_string(carry);
        
    // 순서를 다시 원래대로
	reverse(begin(ret), end(ret));
	return ret;
}

vector<string> dp(10001);
string Fibonacci(int n)
{
	dp[0] = "0", dp[1] = "1";
	for (int i = 2; i <= n; ++i)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	cout << Fibonacci(n) << '\n';
	return 0;
}