[C++] 백준 1003번 : 피보나치 함수

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

1003번: 피보나치 함수

---

문제 풀이

int n	0 출력	1 출력
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

 0부터 5까지 0이 출력되는 횟수와 1이 출력되는 횟수를 보면 어떤 규칙을 알 수 있다.

0이 출력되는 개수는 0부터 시작한 피보나치수열이고, 1은 1부터 시작한 피보나치 수열이다.

따라서 문제에 나온 함수를 살짝만 변형시켜서 사용하면 된다.

 시간 제한이 매우 짧아 피보나치수열을 넣을 배열을 준비해두었다. 이 수열은 함수를 불러올 때 값을 계산해서 저장해 두고 특정 값을 부를 일이 있으면 계산하는 절차를 건너뛰는 기능을 한다.

느낀 점

 처음에 되게 고민했다가 0과 1의 개수를 세다가 우연찮게 발견했다. 다음 문제는 시간이었는데 고수님의 코드를 조금 참고했다 ㅎㅎ..

코드

#include <iostream>

using namespace std;

int arr[50] = { 0,1, };

int fibo(int n) {
	if (n == 0 || n == 1) return arr[n];
	else if (arr[n] == 0) arr[n] = fibo(n - 1) + fibo(n - 2);
	return arr[n];
}

int main() {
	int t, tmp;
	cin >> t;
	for (int i = 0; i < t;i++) {
		cin >> tmp;
		if (tmp == 0) cout << "1 0\n";
		else {
			cout << fibo(tmp-1) << " " << fibo(tmp) << "\n";
		}
	}
}