백준[2748 번] - 피보나치 수 2

문제

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

분석

점화식과 간단한 재귀 호출을 이용하면 쉽게 풀 수 있지만, 메모이제이션을

이용해 풀어 봤다.

필자가 앞서 써둔 글이 있다.

읽고 이 문제를 보면 큰 도움이 될 것이다.

2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

 

구현

long long cache[MAX];
long long fibo(int n)
{
	//base case
	if (n == 1) return 1;
	if (n == 0) return 0;
	//계산한적이 있는 경우
	long long& ret = cache[n];
	if (ret != -1) return ret;

	return ret = fibo(n - 1) + fibo(n - 2);
}

int main()
{
	memset(cache, -1, sizeof(cache));
	int n;
	cin >> n;
	cout << fibo(n);
	return 0;
}

※ 데이터 크기에 주의하자.

 

회고

앞서 메모이제이션에 대해 공부하고 이 문제를 바라보니, 메모이제이션의 필요성을 다시 한번 느끼게 된다.