[백준] C++ 1003(피보나치 함수)

 

#include <iostream>

using namespace std;

int DP[41][2];

int main(void)
{
	int a=0;
	cin>>a;
	
	DP[0][0]=1;
	DP[0][1]=0;
	DP[1][0]=0;
	DP[1][1]=1;
	
	for(int i=2; i<=40; i++)
	{
		DP[i][0]=DP[i-1][0]+DP[i-2][0];
		DP[i][1]=DP[i-1][1]+DP[i-2][1];
	}
	
	for(int i=0; i<a; i++)
	{
		int num=0;
		cin>>num;
		cout<<DP[num][0]<<" "<<DP[num][1]<<endl;
	}
	
	return 0;
}

 

이 문제는 F(i)를 실행시켰을 때 F(0)과 F(1)이 실행되는 횟수를 구하는 문제이다.

그림으로 설명하겠다.

 

느낌이 오는가??

F(4)를 실행시켰을 때 F(0)과 F(1)이 실행되는 횟수는 (F(3)의 횟수 + F(2)의 횟수)이다.

 

즉 

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