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

 

 

<코드>

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

int N, sum;
string a, b, tmp, fibo[10001];
vector<int> ans, num1, num2;

string big_number_sum(string s1, string s2)
{
	string s;

	// 더 긴 수를 s1으로 저장하기
	if (s1.size() < s2.size())
	{
		tmp = s1;
		s1 = s2;
		s2 = tmp;
	}

	// num1, num2 배열을 만드는 과정
	num1.push_back(0);
	num2.push_back(0);

	for (int i = 0; i < s1.size() - s2.size(); i++)
		num2.push_back(0);

	for (int i = 0; i < s1.size(); i++)
		num1.push_back(s1[i] - '0');

	for (int i = 0; i < s2.size(); i++)
		num2.push_back(s2[i] - '0');

	// num배열들의 끝부분부터 덧셈을 하면서 ans벡터에 값 저장
	for (int i = s1.size(); i > 0; i--)
	{
		sum = num1[i] + num2[i];
		if (sum >= 10)
		{
			num1[i - 1]++;
			sum -= 10;
		}
		ans.push_back(sum);
	}

	// 맨 앞자리수 출력
	if (num1.front() != 0) s.push_back('1');

	// ans벡터 거꾸로 출력
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		s.push_back(ans[i]+48);
	}

	num1.clear();
	num2.clear();
	ans.clear();

	return s;
}

int main()
{
	cin >> N;

	fibo[0] = '0';
	fibo[1] = '1';

	for (int i = 2; i <= N; i++)
	{
		fibo[i] = big_number_sum(fibo[i - 1], fibo[i - 2]);
	}
	
	cout << fibo[N];

}

 

풀이 방법

cocoon1787.tistory.com/310

[C/C++] 백준 10757번 - 큰 수 A+B

피보나치수열은 구현하기 쉬우나 입력이 커질수록 수의 크기가 기하급수적으로 증가하므로 문자열 배열로 저장하여 큰 수들의 덧셈을 처리하였습니다. 이 문제를 풀기 전에 위의 "10757번 큰 수 A+B" 문제를 풀어보는 것을 추천드립니다.

 

각각 fibo[1000], fibo[5000], fibo[10000]를 출력한 값입니다.

 

 

www.acmicpc.net/problem/10826

10826번: 피보나치 수 4