[백준] 4150번 피보나치 수

4150번: 피보나치 수

정답이 1000자리 이하라는 말을 보고 눈을 의심했었다.

int나 long long으로는 절대 풀 수 없기 때문에 string을 이용하여 답을 구했다.

 

계산할 때는 숫자를 뒤에서부터 한 자리씩 int로 바꾸어 계산 하였고

계산 완료된 값은 string형으로 배열에 넣어주었다.

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

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

	fibonacci.push_back("0");
	fibonacci.push_back("1");
	
	for (int i = 2; i <= n; i++) {
		int a = fibonacci[i - 1].size(), b = fibonacci[i - 2].size(), res = 0, add = 0;
		string result, temp;
		for (int j = a - 1; j >= 0; j--) {
			if (j - (a - b) >= 0) res = (fibonacci[i - 1][j] - 48) + (fibonacci[i - 2][j - (a - b)] - 48) + add;
			else res = fibonacci[i - 1][j] - 48 + add;
			if (res >= 10) {
				res -= 10;
				add = 1;
			}
			else add = 0;
			temp = result;
			result = to_string(res) + temp;
			if (j == 0 && add == 1) {
				temp = result;
				result = to_string(add) + temp;
			}
		}
		fibonacci.push_back(result);
	}

	cout << fibonacci[n];

	return 0;
}