#1003 피보나치 함수

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

1003번: 피보나치 함수

실버 3의 문제이다. 피보나치 함수는 재귀를 통해 쉽게 구할 수 있지만 재귀를 이용하면 불필요한 계산이 숫자가 늘어날 수록 기하급수적으로 많아져 시간이 오래걸린다. 이 문제는 DP를 이용(메모이제이션을 이용)하여 푸는 문제였다.

 

#include <iostream>
using namespace std;

int memo[41];
int cntone;
int cntzero;

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

int main()
{
  freopen("input.txt","r",stdin);
  int T,N,some;
  cin>>T;
  while(T--){
    cntone=0;
    cntzero=0;
    cin>>N;
    some=fibo(N);

    if(N>=2){
      cout<<fibo(N-1)<<" "<<fibo(N)<<'\n';
    }
    else{
      cout<<cntzero<<" "<<cntone<<'\n';
    }
  }
}

처음 문제를 읽었을 때는 fibo라는 함수에 작성 한것 처럼, 1의 개수를 세는 cntone 과 0의 개수를 세는 cntzero의 값을 늘려가면서 함수를 돌리면 풀릴줄 알았다. 물론 첫번째 테케에서는 통과하였다. 근데 두번째 테케에서는 이상한 값이 나왔다. 잘 생각해보니, 위의 코드 처럼 하면 메모이제이션에 의해 2 이상의 숫자에 대해서는 n이 1과 0일때가 계산이 되지않는다. (이 계산을 하지 않으려고 쓴 방법이 메모이제이션이기 때문이다) 

 

잘 보니 0의 개수와 1의 개수에 규칙이 있었다. 쭉 써놓고 보니 0은 fibo(n-1) , 1은 fibo(n)의 값과 같다는 것을 알게되었다. 물론 N<2 일 때는 N-1이 성립하지 않기때문에 따로 예외 처리를 해주었다!

 

처음 푼 DP문제였는데 생각보다 괜찮았다 ㅎ-ㅎ