BOJ 1103 - 피보나치 함수 (C++)

 

f[i][0] = f[i - 1][0] + f[i - 2][0];
f[i][1] = f[i - 1][1] + f[i - 2][1];

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

1003번: 피보나치 함수

 

BOJ 1103 - 피보나치 함수 (C++)

 

다이내믹 프로그래밍으로 접근하여 풀 수 있는 문제다.

아래 수식을 이용하면 정답을 구할 수 있다.

f[i][0] = f[i - 1][0] + f[i - 2][0];
f[i][1] = f[i - 1][1] + f[i - 2][1];

 

#include <iostream>

using namespace std;

int f[41][41];
int T, N;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	f[0][0] = 1;
	f[0][1] = 0;
	f[1][0] = 0;
	f[1][1] = 1;

	for (int i = 2; i <= 40; i++)
	{
		f[i][0] = f[i - 1][0] + f[i - 2][0];
		f[i][1] = f[i - 1][1] + f[i - 2][1];
	}

	cin >> T;

	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		cout << f[N][0] << " " << f[N][1] << endl;
	}

	return 0;
}