백준 1003번 : 피보나치 함수

링크 : https://www.acmicpc.net/problem/1003

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

왜 조건을 안읽는거야? 제발 읽자. 40보다 작거나 같다는 조건을 안지켜서 계속 틀렸다^~^ 좋겠다 정말 눈알 없어서

#include <iostream>
using namespace std;

int main() {
	int num, elem;
	int a[41]{ 0,1 };

	for (int j = 2; j <= 40; j++) {
		a[j] = a[j - 1] + a[j - 2];
	}

	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> elem;
		if (elem == 0)
			cout << "1 0" << endl;
		else
			cout << a[elem-1] << " " << a[elem] << endl;
	}
	return 0;
}

그래도 꽤 고생했던 만큼 분석해보자.
우선 재귀 함수를 이용해서 문제를 풀게 된다면 시간 초과를 맛보게 된다. 그래서 재귀가 아닌 반복으로 방향을 틀었어야 했다.

반복으로 피보나치 수열을 만들자.

int a[41]{ 0,1 };

for (int j = 2; j <= 40; j++) {
	a[j] = a[j - 1] + a[j - 2];
}

우선 0과 1을 기본 설정으로 바꿔주고 j를 2부터 시작해서 40까지 점화식을 반복해준다. a[j] = a[j - 1] + a[j - 2] 이 피보나치 점화식은 익숙하니 넘어간다.

다음으로 제일 생각하기 어려웠던 부분이고 실제 검색으로 알아낸 부분이다. 복습하자.

index (fibo)	zero	one (==fibo)
0 (0)	1	0
1 (1)	0	1
2 (1)	1	1
3 (2)	1	2
4 (3)	2	3
5 (5)	3	5
6 (8)	5	8
7 (13)	8	13

다음과 같이 된다. index가 0과 1일 때를 제외하고는 규칙적으로 움직이는 것을 확인할 수 있다.

• n-1의 zero + n-1의 one => n의 one
• n-1의 one => n의 zero

그런데 자세히 보면 one의 값은 실제 fibonacchi 값과 동일한 것을 볼 수 있다! 따라서 n-1의 one 호출 수는 n의 fibonacchi 값과 같다는 것을 알 수 있다. 같은 방향으로 n의 zero 호출 수는 n-1의 one 호출 수와 같고 이는 n-1의 fibonacchi 값과 같다.

그래서 실제 재귀로 count하지 않아도 a[elem-1]을 통해 zero를 알 수 있었고 a[elem]을 통해 one을 알 수 있었다.

어렵다. 확실히 한번 해보지 않았다면 머리 아팠을 텐데 풀어봤으니까 미래에는 더 빨리 풀 수 있으리라 기대해본다.

마지막으로 fibonacchi 재귀 함수 복습하고 간다.

int fibonacci(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
    	return fibonacci(n-1) + fibonacci(n-2);
}