[알고리즘] 백준 10826번: 피보나치 수 4 (C++), 문자열 더하기

https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

(미루고 미뤄왔던 문제)

기존에 사용하던 방식의 DP를 사용하는 문제는 맞지만 계속 오버플로우가 나는 현상이 발견된다.

이유는 피보나치 10000이 다음과 같은 값을 가진다.

즉 C++에서 가장 큰 정수 자료형 unsigned long long으로 풀려고 시도할지라도 오버플로우가 나타난다.

유독 C++로 PS 하는 사람들이 이 문제를 겪는다. 처음으로 C++의 단점을 알아낸 거 같다.

Java에서는 BigInteger를 이용하면 금방 풀리는 것으로 알고 있다.

 

---

솔루션

그래서 이것을 어떻게 해야 할지 고민하다가 상식 밖의 솔루션을 찾아냈다.

(+ 참고 https://j3sung.tistory.com/295)

정수형이라는 바운더리 내에서 고민하다가 문자열을 가지고서 더하기를 구현할 생각을 했다는 것이 신기했다.

 

문자열 더하기에 있어서 짚고 넘어가야 할 포인트는

1. 각 수의 길이가 똑같도록 reverse 후에 더 짧은 문자열에 0을 추가해주는 것
2. 더해진 수에서 다음 자릿수로 올라가는 수와 더해지고 남는 수의 처리
3. 마지막에 결괏값을 다시 뒤집어주기

그리고, 이 코드를 보면서 문자열로 구현했다는 생각에 놀라웠지만 아직도 문자열 관련 함수에 부족함이 있음을 느꼈다.

to_string 함수 기억해둬야겠다.

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

string sum(string a, string b) {
	int num;
	int carry = 0; // 올라가는 수
	string result;

	// 각 수를 뒤집어서 길이가 같을 때까지 길이가 작은 쪽에 앞자리에 0을 넣어준다
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	while (a.size() < b.size()) {
		a += '0';
	}
	while (a.size() > b.size()) {
		b += '0';
	}

	for (int i = 0; i < a.length(); i++) { // a와 b의 length가 같아서 둘 중 아무거나 해도 상관 없음
		num = ((a[i] - '0') + (b[i] - '0') + carry) % 10; // 더해주고 해당하는 자리에 남는 수
		result += to_string(num);
		carry = ((a[i] - '0') + (b[i] - '0') + carry) / 10;
	}
	if (carry != 0) {
		result += to_string(carry);
	}

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

	return result;
}

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

	string cache[10001];

	cache[0] = '0';
	cache[1] = '1';

	for (int i = 2; i <= n; i++) {
		cache[i] = sum(cache[i - 1], cache[i - 2]);
	}

	cout << cache[n];
	return 0;
}

---

반드시 업 솔빙이 필요한 문제!