백준 11444번 : 피보나치 수 6

 

 

문제 접근

---

1. 입력으로 주어지는 n의 최대 크기는 100경이므로, $O(n)$으로는 절대 풀이하지 못한다.
2. 피보나치 수열의 식 $F(n) = F(n-1) + F(n-2)$을 변형해서 접근하자.
   
     일반항 $F(n) = \frac{1}{\sqrt{5}} \times (\frac{1+\sqrt{5}}{2})^2 - \frac{1}{\sqrt{5}} \times (\frac{1-\sqrt{5}}{2})^2$로 변형하여 바로 풀이하자.

 

 

일반항 유도 과정

 

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

11444번: 피보나치 수 6

 

 

 

문제 코드 : 일반항으로 시도 - 부동 소수점 이슈로 실패... 인생.. 

---

#include <iostream>
#include <cmath>

using namespace std;

long double PowerModByDivideConquer(long double value, int exponent)
{
	long double result = 1;

	while (exponent)
	{
		if (exponent % 2 == 1)
		{
			result = fmod(result * value, 10000000000);
		}

		value = fmod(value * value, 10000000000);
		exponent /= 2;
	}

	return result;
}

int main(void)
{
	// remove below line when code copy
	freopen("input.txt", "r", stdin);

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	long double ans;

	cin >> n;


	for (int i = 0; i <= n; ++i)
	{
		ans = (PowerModByDivideConquer((1 + sqrt(5)) / 2, i) - PowerModByDivideConquer((1 - sqrt(5)) / 2, i)) / sqrt(5);

		cout << int(floor(ans + 0.5)) % 1000000007 << '\n';
	}

	return 0;
}

 

 

    main의 for문 같은 경우는 피보나치 수열이 제대로 나오는지 확인해보기 위해 추가한 구문이다. 결과는 아래와 같이 부동 소수점 이슈로 인해 실패했다.

 

    각 계산의 결과를 10000000000으로 나눈 건 문제를 풀이할 때 모듈러 연산 특성을 잊은 채, 단순하게 윗 자릿수를 무시하고 마지막에 1000000007을 나머지 연산 처리해 주려고 이렇게 풀이했다.

 

결과 : n이 60을 넘어갈 때 쯤부터 이상이 생긴다.

 

 

 

문제 코드 : 개선

---

#include <iostream>
#include <map>

using namespace std;

map<int, int> cache;

long long Fibonacci(long long n)
{
	if (cache[n])
		return cache[n];


	if (n % 2)
		return cache[n] = (Fibonacci((n + 1) / 2) * Fibonacci((n + 1) / 2) + Fibonacci((n - 1) / 2) * Fibonacci((n - 1) / 2)) % 1000000007;

	else
		return cache[n] = (Fibonacci(n / 2) * (Fibonacci(n / 2 + 1) + Fibonacci(n / 2 - 1))) % 1000000007;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cache[0] = 0;
	cache[1] = 1;
	cache[2] = 1;

	long long n;

	cin >> n;

	cout << Fibonacci(n);

	return 0;
}

 

 

    문제를 풀 당시에 $O(n)$으로는 절대 풀 수 없다는 걸 알면서 $O(\log{n})$으로 접근할 생각은 하지 못했다.. 그냥 일단 다시 수식을 풀이하면서 전개를 하는데 $F(n) = F(k+1)F(n-k) + F(k)F(n-k-1)$로 풀이할 수 있다는 걸 깨달았다.

 

    이때 $k=\frac{n}{2}$라면, $O(\log{n})$으로 풀 수 있을 것 같아서, n이 홀수와 짝수일 때 식을 정리한 뒤 이를 위와 같이 구현했고, 결과적으로 성공했다.

 

 

분할 수식 유도 과정

 

 

 

느낀 점

---

    아니, 이게 왜 골드 2야. 수학적으로 접근해야 되니 이번 알고리즘 레콩키스타의 목적에도 부합하지만 처음부터 이렇게 강한 문제가 나올 줄은 몰랐다. 이 문제만 거의 6시간은 붙들고 있던 것 같다. 그래도 수식으로 접근하는 것에 조금씩 익숙해지면 점점 빨라지겠지..?

 

    하긴 삽질을 많이하긴 했다. 가장 먼저 부동 소수점 이슈가 생기면 빠르게 견적을 내고, 다른 방법을 사용할 생각을 해야 되는데 이전 방법에 매몰돼서 성과 없이 부동 소수점 이슈만 붙잡고 있기도 했다. 이래서 가설을 세우고 가능성을 따져봐야되는데 그저 무지성으로 계속 시도했다.

 

    여기에 더해 두번째 방법에서는 제대로 잘 풀어놓고 main 쪽 입력을 받을 때 int로 받아서 1시간 정도 '왜 이럼..?'하면서 다시 삽질을 이어갔다. 아니, 상식적으로 int로 100경을 입력받을 수 있겠냐고~

 

    .. 아무튼 삽질은 많이 했지만 그만큼 많이 얻을 수 있었던 문제였다. 이번에 얻은 것들을 정리하면 다음과 같다.

 

1. 모듈러 연산에 대한 이해
2. 부동소수점 이슈에 대한 이해
3. 수학적으로 접근하는 것에 대한 경험치 (아~~주 약간ㅋㅋ)
4. STL map의 사용법 (Red-Black Tree로 구현됐다는데 한번 직접 구현해 보면 좋을 것 같다.)

 

    다른 풀이 방법을 찾아보니까 행렬을 이용하는 방법도 있는데 해당 방법은 2749번 : 피보나치 수 3에서 시도해보려고 한다. 근데 배경 지식이 없으면 행렬로 푼다는 거 어떻게 알지..? 구글링이 답인가?

2749번: 피보나치 수 3

 

    한번 제대로 증명해가면서 풀어보니까 피보나치 수열 문제가 수학적으로 접근하는 습관을 키우기 좋아 보여서 class 5 문제에 국한되지 않고, 일단 피보나치 수열 쪽 문제를 계속 풀어봐도 좋을 것 같다.

 

    여기까지가 풀이 후기다. 아래에 간단하게 느낀 점을 정리하고 마무리짓도록 하겠다.

 

 

1. 누누이 말하지만 생각을 하고 접근하자.
   
     무지성으로 '어떻게 한 번 안될까?' 하다가는 내가 어떻게 돼버린다.. 제대로 생각하는 습관은 확장하기가 어려워서 그렇지 한번 확장하면 자연스럽게 이어지니 계속 고민하고, 고민하도록 하자.
   
   
2. 무언가 방법이 통하지 않는다면 빠르게 다시 한번 가능성을 생각해 보자.
   
     이전 방법에 투자한 시간이 매몰되어 가능성 검증을 뒤로하는 건 도박에 가깝다. 확실한 문제 해결을 하자.
   
   
3. 쉬운 방법이 생각났으면 제발 그냥 해라.
   
     괜한 고집에 '이것도 될 것 같은데..'하지 말고, 일단 쉬운 방법이 생각났으면 그걸로 되는지 확인해라. 기존 방법은 그 이후에 생각해 봐도 늦지 않다.
   
   
4. 입출력 같은 사소한 부분을 가장 확실하게 구현하자.
   
     처음 한 번만 조건 인지하고 확실하게 하면 이후의 시간 낭비를 줄여준다.
   
   

 

이걸로 class 4 은장 획득! (class 1은 겸사겸사.. 희희)