[알고리즘] 백준 4150번: 피보나치 수 (C++), DP인데 배열을 안 쓴다고?

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

4150번: 피보나치 수

 

이 문제는 저번에 풀었던 문제와 똑같다고 생각했다. (https://www.acmicpc.net/problem/10826)

당연히 포인트도 똑같이 수를 문자열로 바꾸어 합을 구하는 함수를 구현하는 게 포인트라고 생각했다.

 

똑같은 풀이를 제출했으나 '메모리 초과'라는 오류를 받는다.

메모리가 크게 발생할 곳은 배열 밖에 없다고 생각했지만 배열을 안 쓰고서 구현할 수 있을까 생각했다.

 

[솔루션에 도출하기까지의 아이디어]

1. 어차피 원하는 건 result

2. 점화식에 필요한 건 2개의 fibo(n - 1), fibo(n - 2)

3. 변수 2개로 해결할 수는 없을까?

>> 합이 나올 때마다 result에 넣고, 한 번 더 합을 진행해야 한다면 기존 2번 변수를 1번 변수, result 값을 2번 변수에 넣으면 되겠다는 생각이 들었다.

>>>> swap에서 영감받음

 

[Before]

cache[1] = "1";
	cache[2] = "1";

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

[After]

if (n == 0) {
	result = "0";
}
if (n == 1) {
	result = "1";
}

for (int i = 2; i <= n; i++) {
	result = strSum(value1, value2);
	value1 = value2;
	value2 = result;
}

 

---

[전체 소스 코드]

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

int n;

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

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

	int alone;
	int carry = 0;
	string result;
	for (int i = 0; i < a.length(); i++) {
		alone = ((a[i] - '0') + (b[i] - '0') + carry) % 10;
		result += to_string(alone);
		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() {
	cin >> n;
	vector<string> cache(n + 1);
	string value1 = "0";
	string value2 = "1";

	string result;

	if (n == 0) {
		result = "0";
	}
	if (n == 1) {
		result = "1";
	}

	for (int i = 2; i <= n; i++) {
		result = strSum(value1, value2);
		value1 = value2;
		value2 = result;
	}

	cout << result;
	return 0;
}

---

오랜만에 기존 지식의 틀을 깨는 문제였다. 예전엔 이런 문제 싫었는데 이제는 틀을 넓히는 느낌이라 좋다!