기본 콘텐츠로 건너뛰기

1003 : The Function of Fibonacci (Dynamic Programming) [C,C++]

int fibonacci(int n)

It is a problem of overriding the Fibonacci function to find out how many times fibonacci(0) and fibonacci(1) were called.

 Before we solve this problem, I will describe the Fibonacci Sequence.

 The Fibonacci sequence has the following rules.
fibonacci(0) = 1, fibonacci(1) = 1,
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

In the example, If 'n' is 3,
=> fibonacci(3) = fibonacci(3-2) + fibonacci(3-1)
=> fibonacci(3) = fibonacci(1) + fibonacci(2)
=> fibonacci(3) = fibonacci(1) + fibonacci(1) + fibonacci(0) = 3.
Because of these rules, we have to calculate the fibonacci sequence repeatedly.
It does not matter if the value is small, but in the opposite case
it is necessary to apply DP which is an algorithm to save the calculated value.

 Let's solve it with DP.
<pesudo code>

*Source of the problem = https://www.acmicpc.net/problem/1003
*문제 출처 : BAEKJOON ONLINE JUDGE






















라벨:





























댓글











댓글 쓰기




















이 블로그의 인기 게시물





















11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]




























 1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 !     DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다!     수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다.     왜 곱셈의 역원을 구해야하는가?     N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문!     곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면       p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요.     분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다.     DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다.     그러므로 총 시간 소요는 O(N+LogP)     long  long  BinomialCoefficient :: GetNum ( int  N ,  int  K )  {      this - > Factorial [ 1 ]  =  1 ;      for  ( int  i =  2 ;  i < =  4000000 ;  i + + )          this - > Factorial [ i ]  =  ( this - > Factorial [ i -  1 ]  *  i )  %  P ;                       this - > Invert [ 4000000 ]  =  this - > Pow_DC ( this - > Factorial [ 4000000 ] ,  P -  2 ) ;      for  ( int  i =  4000000  -  1 ;  i >  0 ;  i - - )           this - > Invert [ i ]  =  ( this - > Invert [ i +  1 ]  *  ( i +  1 ) )  %  P ;            if  ( N = =  K | |  K = ...




















댓글 쓰기









자세한 내용 보기





























1978 : 소수 찾기 [C++]




























# include < iostream >  # include < vector >   using  namespace  std ;   int  main ( )  {   cin . tie ( NULL ) ;    vector < int >  Primes ;    Primes . push_back ( 2 ) ;   Primes . push_back ( 3 ) ;   for  ( int  i =  4 ;  i <  1000 ;  i + + )   {    bool  IsPrime =  true ;     if  ( i %  2  = =  0  | |  i %  3  = =  0 )     continue ;    for  ( int  j =  4 ;  j <  i ;  j + + )    {     if  ( i %  j = =  0 )     {      IsPrime =  false ;      break ;     }    }     if  ( IsPrime )     Primes . push_back ( i ) ;   }    int  N ,  Count =  0 ;   cin  > >  N ;    for  ( int  i =  0 ;  i <  N ;  i + + )   {    int  Input ;    cin  > >  Input ;     for  ( int  j =  0 ;  j <  Primes . size ( ) ;  j + + )     if  ( Input = =  Primes [ j ] )      Count + + ;   }    cout  < <  Count < <  " \n " ;    return  0 ;  }  




















댓글 쓰기









자세한 내용 보기