[C/C++] 코드업 1916 : (재귀함수) 피보나치 수열 (Large)

문제풀이

이 문제는 메모이제이션을 이용하여 재귀 함수 계산 시간을 단축하는 문제임.

이전 문제에서는 단순히 함수 호출을 반복해서 하였으나, 이번 문제는 배열에 결과값을 적고, 값이 필요하면 '함수를 호출하는 것'이 아니라 '배열에서 이전에 계산한 값'만 불러오게 되어 시간이 단축되는 구조임. 중복해서 함수를 계속 부르는 것보다 배열에서 가져다 쓰는 게 빠름.

 

메모이제이션은 top down과 bottom up이 있는 데, 사실 이러한 개념보다는 아래 문장을 외워보는 게 좋음.

'값이 배열에 적혀 있지 않으면 배열에 적은 후 리턴하고, 값이 이미 적혀 있다면 적힌 값을 리턴함.'

이것만 잊지 않는다면 웬만한 메모이제이션 문제를 모두 풀 수 있음.

 

그리고 잘 보면 아래에 %10009로 나머지 구하는 걸 거의 모든 결과 연산에 적어 두었는 데, 이렇게 하는 게 맞음.

어떨 때는 'a%10009+b%10009하고 (a+b)%100009는 다를 수 있지 않나?' 싶은데, mod 계산에서 보면 이러한 계산은 괄호로 묶어서 하든 풀어서 하든 상관 없음. a, b 각각만 보더라도 오버플로우가 발생할 수 있으니 많이 해 두는 게 좋음.

 

이렇게 하면 되지만 혹시해서 몰라 long long 타입을 사용하였음.

소스코드

#include <iostream>
#define MAX 210
using namespace std;

long long  arr[MAX]={0,1,1};

long long fibbo(int a){
	if (arr[a]==0)
	{
		arr[a]=fibbo(a-1)%10009+fibbo(a-2)%10009;
		return arr[a]%10009;
	}
	else
	{
		return arr[a]%10009;
	}
}

int main()
{
    int n;
    cin>>n;
    cout<<fibbo(n)%10009;
}