문제

문제 해결 전략

동적 프로그래밍을 이용하여 문제의 규칙성을 파악하고 문제의 규칙성에 맞는 코드를 작성해야 된다고 생각했다. 메모이제이션을 이용하여 피보나치 수열을 기록하고 수열이 기록되지 않았을때는 0으로 초기화 된 값을 앞서 계산된 값을 이용하여 계산을 O(n) 복잡도를 갖게 된다.

코드

#include<iostream>
#include<vector>
using namespace std;
#define N 40
int fib[N+1] = {0, 1, };

int fibo(int n){
	if(n == 1 || n == 0){return fib[n];}
	else if(fib[n] == 0)
		fib[n] = fibo(n-1) + fibo(n-2);
	return fib[n];
	
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	int n;

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

다사다난 했다....