Baekjoon 백준 2747, 2748, 10870번 피보나치 수

이제서야 dp가 뭔지 왜 쓰는지 언제 쓰는지 쳐다보고 있다...

 

#include <stdio.h>
#include <string.h>

int fibo(int dp[], int n)
{
	if (dp[n] != -1) 
	{
		return dp[n];
	}
	if (n == 0)
	{
		dp[n] = n;
	}
	else if (n == 1)
	{
		dp[n] = 1;
	}
	else 
	{
		dp[n] = fibo(dp, n - 1) + fibo(dp, n - 2);
	}

	return dp[n];
}

int main()
{
//2748의 경우 N이 90까지라 dp[91]
//그리고 90일 경우 value가 크기 때문에 
//long long dp[91], long long fibo로
	int N = 0,  dp[46];
	scanf("%d", &N);

	for (int i = 0; i <= N; i++)
		dp[i] = -1;

	printf("%d\n", fibo(dp, N));
}

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

2747번: 피보나치 수