[C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이)

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

11444번: 피보나치 수 6

11444: 피보나치 수열 문제

 

맨 처음에 다른 문제처럼 DP로 풀려고 했지만 너무 범위가 커 메모리초과가 나왔다.

 

구현!!

이 문제와 같이 입력의 수가 과도하게 크고 DP를 사용해야할 상황일 때  (1.)항상 점화식을 2개로 나눠서 풀 수 있도록 생각을 해야한다. 특히 (2.)한번 지난간 곳을 저장해둬서 한번 지난 곳은 다시 못 지나가게 만들어 시간을 줄여야할 필요도 있다.

 

 1)

 그래서 점화식을 나누기 위해 머리를 굴렸지만 결국 두개로 나누지 못했다. 사실 거의 다 오긴 했지만 마지막에...

그렇게 다른 블로그에서 힌트를 얻어 점화식을 완성하였다.

 

f(n)=f(n/2)(2f(n/2-1)+f(n/2)) (n이 짝수일 때)

f(n)=f(n+1/2)^2+f(n-1/2)^2  (n이 홀수일 때)

 

f(n)=f(n-1)+f(n-2)라는 식을 전개해 나가면 임의의 k에 대해 성립하는 식을 만들어주면

f(n)=f(k+1)f(n-k)+f(k)f(n-k-1)이 된다.

이 식은 결국 n에 대한 식이고 모든 k에 대해서 성립하기 때문에 k에 적당한 값을 넣어 f(n)=f(n/2)....꼴이 나오도록 만들어주면 된다

n이 짝수일 때는 k=n/2를 넣었고 n이 홀수일 때는 k=n을 넣고 f(2n+1)=f(n)...꼴을 만들어주고 n에다가 n-1/2 를 대입해주었다.

 

2)

 이렇게 하면 사실상 거의 끝났다고 볼 수 있다. 맨 처음 써 있다싶이 점화식을 2개로 나누어 시간복잡도를 O(logn)으로 낮추는 것에 성공했기 때문에 이번에는 한번 지나간 곳을 저장해두기 위해 map을 사용하였다. map의 메모리 범위는 매우 큰 편이기 때문에 웬만해서는 대부분의 경우를 커버 가능하다.

map<long long int,long long int> m 으로 선언하고 

만약 fibo()에 들어온 수가 이미 map m에 있던 수라면 map에서 꺼내서 나오게 하여 중복된 연산을 최소화하였다.

 

또한 최대한 재귀함수를 적게 부르는 것이 좋기 때문에 fibo()의 값을 변수로 저장하고 이 변수로 점화식을 만들어주는 것이 효과적이다. 문제에서 1000000007로 나눈 나머지를 구하라고 했으므로 map에 들어가있는 수 역시 1000000007로 나눈 나머지를 저장해주고 #define MOD 1000000007 으로 선언해 가독성을 높였다.

 

#include <iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>
#define MOD 1000000007

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
map<long long int,long long int> m;

int fibo(long long int n)
{
  if(n==0)
    return 0;
  if(n==1) return 1;
  if(n==2) return 1;
  if(m.count(n)>0) return m[n];
  
  if(n%2==0) // 짝수일때
  {
    long long int tmp1,tmp2;
    tmp1=fibo(n/2-1);
    tmp2=fibo(n/2);
    m[n]=(tmp2*(2*tmp1+tmp2))%MOD; 
    return m[n];
  }
  else // 홀수일때
  {
    long long int tmp1,tmp2;
    tmp1=fibo((n-1)/2);
    tmp2=fibo((n+1)/2);
    m[n]= (tmp1*tmp1+tmp2*tmp2)%MOD;
    return m[n];
  }
    
}


int main() {
 long long int n;
  cin>>n;
  int result=fibo(n);
  cout<<result;
}