[BOJ] 1003_피보나치 함수 with cpp

# 생각

dp를 이용하여 해결할 수 있다

 

테이블 정의

fibo[i][k] = 숫자 i가 0 또는 1을 호출한 횟수

 

점화식

fibo[i][k] = fibo[i-1][k] + fibo[i-2][k]

 

초기값

fibo[0][0] = fibo[1][1] = 1

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int fibo(int n, int index)
{
	int f[44][2] = {};
	f[0][0] = f[1][1] = 1;
	for (int i = 2; i <= n; i++)
	{
		f[i][0] = f[i - 1][0] + f[i - 2][0];
		f[i][1] = f[i - 1][1] + f[i - 2][1];
	}
	return f[n][index];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int TC;
	cin >> TC;
	while (TC--)
	{
		int n;
		cin >> n;
		cout << fibo(n, 0) << ' ' << fibo(n, 1) << '\n';
	}
}

 

---

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

1003번: 피보나치 함수