백준 10826번: 피보나치 수 4

[문제 링크]

10826번: 피보나치 수 4

---

dp의 메모이제이션 기법을 이용하는 전형적인 피보나치 수열 문제였다.

 

다만, n의 최대가 10000인데, 피보나치 수열은 갈수록 값이 어마어마하게 커지기 때문에 n의 값이 클경우 unsigned long long 자료형에도 담을 수 없을 정도로 커지게 된다.

 

따라서 숫자를 문자열로 표현한 다음, 두 문자열의 합을 구해주는 sum 함수를 구현하여 이와 같은 문제를 해결하였다.

---

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

string memo[10001];

string sum(string a, string b) {
	string result;
	int up = 0;

	// 자리수가 다를 경우 뒤에 있는 수가 반드시 자리수가 큼
	while (!b.empty()) {
		if (!a.empty()) {
			int num1 = a.back() - '0';
			int num2 = b.back() - '0';
			a.pop_back();
			b.pop_back();

			int sum = num1 + num2 + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
		else {
			int num = b.back() - '0';
			b.pop_back();

			int sum = num + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
	}
	if (up == 1)
		result.push_back('1');

	reverse(result.begin(), result.end());

	return result;
}

string bottomUp(int n)
{
	memo[0] = '0', memo[1] = '1';
	
	for (int i = 2; i <= n; i++) {
		memo[i] = sum(memo[i - 2], memo[i - 1]);
	}
	
	return memo[n];
}

int main(void)
{
	int n;
	cin >> n;

	cout << bottomUp(n) << endl;
	
	return 0;
}

10000번째 피보나치 수열은 정말 어마어마한 숫자이다.....