티스토리 뷰

이제서야 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번: 피보나치 수

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

 

댓글
댓글쓰기 폼

티스토리 방명록