기본 콘텐츠로 건너뛰기

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






















라벨:





























댓글











댓글 쓰기




















이 블로그의 인기 게시물




















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 ;  }  




















댓글 쓰기









자세한 내용 보기




























10828 : 스택 [Python]




























Stack =  [ ]   def  push ( num ) :      Stack . append ( int ( num ) )  def  pop ( ) :      if  len ( Stack )  >  0 :          print ( Stack . pop ( ) )      else :          print ( - 1 )  def  size ( ) :      print ( len ( Stack ) )  def  empty ( ) :      if  len ( Stack )  ==  0 :          print ( 1 )      else :          print ( 0 )  def  top ( ) :      if  len ( Stack )  >  0 :          print ( Stack [ len ( Stack )  -  1 ] )      else :          print ( - 1 )   TestCase =  int ( input ( ) )   while  TestCase >  0 :      Command =  input ( )       if  Command ==  'top' :          top ( )      elif  Command ==  'pop' :          pop ( )      elif  Command ==  'empty' :          empty ( )      elif  Command ==  'size' :          size ( )      else :          push ( Command [ 5 : ] )       TestCase - =  1   




















댓글 쓰기









자세한 내용 보기