기본 콘텐츠로 건너뛰기

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






















라벨:





























댓글











댓글 쓰기




















이 블로그의 인기 게시물



















6359 : 만취한 상범 (Dynamic Programming) [C++]




























# include < iostream >  # include < vector >   using  namespace  std ;   int  Num_of_Divisor ( int  n )  {      int  Count =  0 ;           for ( int  i =  1 ;  i < =  n ;  i + + )          if ( n %  i = =  0 )              Count + + ;           return  Count ;  }   int  main ( )  {      int  Testcase ;      cin  > >  Testcase ;           while ( Testcase - - )      {          int  Rooms ;          cin  > >  Rooms ;                   vector < int >  Prisons ;          for ( int  i =  0 ;  i <  Rooms ;  i + + )              Prisons . push_back ( 0 ) ;                   for ( int  i =  1 ;  i <  Prisons . size ( )  +  1 ;  i + + )          {              if ( ( Num_of_Divisor ( i )  %  2 )  = =  0 )                  Prisons [ i - 1 ]  =  0 ;              else                  Prisons [ i - 1 ]  =  1 ;          }                   int  Fleer =  0 ;                   for ( int  i =  0 ;  i <  Prisons . size ( ) ;  i + + )              if ( Prisons ...




















댓글 쓰기









자세한 내용 보기




























11004 : K번째 수 [C++]




























# include < iostream >  # include < cstdio >  # include < algorithm >   int  main ( )  {   int  * Number =  new  int [ 5000000 ] ;    int  N ,  K ;   scanf ( " %d %d " ,  & N ,  & K ) ;    for  ( int  i =  0 ;  i <  N ;  i + + )    scanf ( " %d " ,  Number [ i ] ) ;    std :: sort ( Number ,  Number +  N ) ;    printf ( " %d " , Number [ K -  1 ] ) ;    return  0 ;  }  




















댓글 쓰기









자세한 내용 보기






























1149 : RGB Street Coloring (Dynamic Programming) [C,C++]




























 The key to this problem lies in understanding the principles.    Let me explain the algorithm to solve the problem by using DP.      First, you need the same storage space like input data's size.     When you draw any color of the nth house, the space will contain the minimum value.   If you paint the red in the second house, this value is sum of blue or green of the first house.      You must use DP because you must use the previous value.    Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.      If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.      Therefore, the minimum value can be found in the value of the storage space (n-1) index.         <pesudo code>      *Source of the problem =  https://www.acmicpc.net/problem/1149    *문제 출처  : BAEKJOON ONLINE JUDGE     




















댓글 쓰기









자세한 내용 보기