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

 

 

 

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

 

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

 

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

---

 

 

문제 해결

피보나치 수열을 10000번째까지 구하는 일은 어떠한 프로그래밍 언어도 숫자로는 나타낼 수 없습니다. 이유는 그 수가 상상이상으로 무지막지하게 크기 때문인데요.

 

실제로 구해본 결과는 아래 사진과 같았습니다.

10000번째 피보나치 수

 

(진짜 큽니다 ; 처음엔 코드 잘못 작성한 줄)

 

따라서 문자열로 구현해야 합니다. 저는 올림수를 고려하여 맨 뒤를 일의 자리가 아닌, 맨 앞을 일의 자리로 두었습니다. 마지막에 출력할 때만 거꾸로 출력하면 되니까요.

 

carry를 0으로 초기화하고, 각 자리를 더할 때 같이 더해줍니다. 그러고 더한 결과 sum의 일의 자리를 반환 문자열 res에 넣고, carry = sum / 10으로 설정합니다. 그러면 carry는 sum이 10 미만일 때 0, 10 이상일 때는 1로 알아서 바뀌게 됩니다.

 

코드로 살펴보겠습니다.

 

 

 

 

코드

#include <iostream>
using namespace std;

int n;
string fib[10001] = { "0","1" };

string fib_sum(string a, string b) {

	string res;

	int alen = a.size(),
		blen = b.size(),
		pos = 0,
		carry = 0,
		sum;

	while (pos < alen && pos < blen) {
		sum = (a[pos] - '0') + (b[pos] - '0') + carry;
		res += sum % 10 + '0';	// 일의 자리 숫자를 문자로 변환하여 반환 문자열에 추가
		carry = sum / 10;
        	pos++;
	}

	while (pos < alen) {
		sum = (a[pos] - '0') + carry;
		res += sum % 10 + '0';
		carry = sum / 10;
		pos++;
	}

	while (pos < blen) {
		sum = (b[pos] - '0') + carry;
		res += sum % 10 + '0';
		carry = sum / 10;
		pos++;
	}

	if (carry) res += carry + '0';	// 마지막 올림수가 있는 경우 문자열에 추가

	return res;
}

int main() {
	cin >> n;

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

	for (int i = fib[n].size() - 1; i >= 0; i--)
		cout << fib[n][i];
}