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

문제

[C++] 백준 10826: 피보나치 수 4 SILVER 5
https://www.acmicpc.net/problem/10826

 

---

 

접근 방법

백준 10826번은 N번째 피보나치 수를 출력하는 문제다.
하지만 일반적인 피보나치 문제와 달리 값의 크기가 매우 커진다.

 

예를 들어 N이 커지면 피보나치 값은 수백 자리 이상의 정수가 되기 때문에long long 같은 기본 정수 타입으로는 저장할 수 없다.

그래서 이 문제는 큰 정수(Big Integer) 를 직접 구현해야 한다.
이를 위해 문자열(string) 을 이용해서 덧셈을 구현했다.

 

피보나치 점화식은 다음과 같다.

F(n) = F(n-1) + F(n-2)

하지만 문자열끼리 바로 덧셈이 되지 않기 때문에 문자열 덧셈 함수 add()를 만들어 계산했다.

 

문자열 덧셈의 동작 방식은 다음과 같다.

1. 두 문자열을 뒤집어서 1의 자리부터 계산하도록 만든다.
2. 각 자리 숫자를 더하면서 carry(올림) 를 처리한다.
3. 결과 문자열을 다시 뒤집어서 정상적인 숫자 형태로 만든다.

이렇게 구현하면 매우 큰 숫자도 문제없이 계산할 수 있다.

 

이후 피보나치 수열은 DP 방식으로 계산했다.

vector<string> fibo(n + 1, "0");
fibo[1] = "1";

for (int i = 2; i <= n; i++)
    fibo[i] = add(fibo[i - 1], fibo[i - 2]);

문자열 덧셈을 이용해 이전 두 값을 더하면서 fibo[n]을 구하면 된다.

 

구현 시 주의할 점

• n이 0인 경우 처리
  • 만약 n이 0이라면 벡터 크기는 1이 되고 유효한 인덱스는 fibo[0]뿐이다.
    그런데 바로 fibo[1] = "1"; 에 접근하면 범위를 벗어나 런타임 에러가 발생한다.
• 큰 정수 덧셈을 쉽게 구현하기 위해 문자열을 뒤집어서 1의 자리부터 계산하도록 하는 것이 중요하다.
  • 대신 마지막에 결과 ret를 리턴할 때도 reverse를 해주어야 한다.

reverse(a.begin(), a.end());
reverse(b.begin(), b.end());

 

---

 

코드

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

string add(string a, string b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string ret = "";
	int carry = 0, index = 0;

	while (index < a.size() && index < b.size())
	{
		int num = (a[index] - '0') + (b[index] - '0') + carry;
		carry = num / 10;
		num %= 10;
		ret += char(num + '0');
		index++;
	}
	while (index < a.size())
	{
		int num = (a[index] - '0') + carry;
		carry = num / 10;
		num %= 10;
		ret += char(num + '0');
		index++;
	}
	while (index < b.size())
	{
		int num = (b[index] - '0') + carry;
		carry = num / 10;
		num %= 10;
		ret += char(num + '0');
		index++;
	}

	if (carry > 0)
		ret += char(carry + '0');

	reverse(ret.begin(), ret.end());
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

	vector<string> fibo(n + 1, "0");
	if (n != 0)
	{
		fibo[1] = "1";
		for (int i = 2; i <= n; i++)
			fibo[i] = add(fibo[i - 1], fibo[i - 2]);
	}
	cout << fibo[n];

	return 0;
}